<Home>Teaching><MATH 131A (Winter 2025)>Homework 1

Homework 1

Table of Contents

Exercise 1.9

  1. Decide for which integers the inequality 2n>n22^n > n^2 is true.
  2. Prove your claim in (1) by mathematical induction.
Solution.

  1. You can check by hand that n=0,1n = 0, 1 and n≥5n \geq 5 are the only possible nn's that work.

  2. We will prove the statement

    P(n)=‘‘2n>n2"∀n≥5.P\p{n} = ``2^n > n^2" \quad \forall n \geq 5.

    Base case: (n=5n = 5)

    25=32>25=522^5 = 32 > 25 = 5^2, so the base case holds.

    Inductive step:

    Assume that 2n>n22^n > n^2. We need to show that 2n+1>(n+1)22^{n+1} > \p{n+1}^2. We start on the left-hand side:

    2n+1=2⋅2n>2n22^{n+1} = 2 \cdot 2^n > 2n^2

    by the inductive hypothesis. To complete the proof, we need to show that 2n2>(n+1)22n^2 > \p{n+1}^2. Since n≥5n \geq 5, we have

    2n2=n2+n2≥n2+5n=n2+2n+3n>n2+2n+1=(n+1)2.\begin{aligned} 2n^2 = n^2 + n^2 &\geq n^2 + 5n \\ &= n^2 + 2n + 3n \\ &> n^2 + 2n + 1 \\ &= \p{n + 1}^2. \end{aligned}

    Thus, we have shown 2n+1>(n+1)22^{n+1} > \p{n+1}^2.

Common Mistakes

Some of the proofs of the inductive step looked like this:

2n+1>(n+1)2  ⟹  2n2>n2+2n+1  ⟹  n2−2n−1>0,2^{n+1} > \p{n + 1}^2 \implies 2n^2 > n^2 + 2n + 1 \implies n^2 - 2n - 1 > 0,

which is true. Thus, 2n+1>(n+1)22^{n+1} > \p{n + 1}^2 is true.

This issue with this is that the proof is structured like this:

(what we want to show)  ⟹  (something true),\p{\text{what we want to show}} \implies \p{\text{something true}},

but a correct proof must be structured like this:

(something true)  ⟹  (what we want to show).\p{\text{something true}} \implies \p{\text{what we want to show}}.

In general, these are two completely different statements (they are converses of each other). For instance,

1=−1  ⟹  1=12=(−1)2=1,1 = -1 \implies 1 = 1^2 = \p{-1}^2 = 1,

but clearly 1≠−11 \neq -1. In particular, we can't reverse the "  ⟹  \implies" arrows.

Exercise 2.5

Show (3+2)23\p{3 + \sqrt{2}}^{\frac{2}{3}} is not a rational number.

Solution.

I will present two solutions. Either one is perfectly valid, though it'd be good for you to learn both techniques.

Solution 1 (by irrationality of 2\sqrt{2})

Set x=(3+2)23x = \p{3 + \sqrt{2}}^{\frac{2}{3}}. Then

x3=(3+2)2=11+62  ⟹  2=x3−116. x^3 = \p{3 + \sqrt{2}}^2 = 11 + 6\sqrt{2} \implies \sqrt{2} = \frac{x^3 - 11}{6}.

Thus, x∈Q  ⟹  2∈Qx \in \Q \implies \sqrt{2} \in \Q, which is not possible, so it must be the case that x∉Qx \notin \Q.

Solution 2 (by the rational roots theorem)

If we continue the above calculation, then

x3−11=62  ⟹  x6−22x3+121=72  ⟹  x6−22x3+49=0. x^3 - 11 = 6\sqrt{2} \implies x^6 - 22x^3 + 121 = 72 \implies x^6 - 22x^3 + 49 = 0.

This polynomial has all integer coefficients, so we may apply the rational roots theorem, which tells us that the only possible rational roots are ±1,±7,±49\pm 1, \pm 7, \pm 49. It's easy to check that none of these are roots, so the polynomial has no rational roots, which means xx must be irrational.

Exercise 2.7

Show (3+2)23\p{3 + \sqrt{2}}^{\frac{2}{3}} is not a rational number.

Solution.

Show the following irrational-looking expressions are actually rational numbers:

  1. 4+23−3\sqrt{4 + 2\sqrt{3}} − \sqrt{3}, and
  2. 6+42−2\sqrt{6 + 4\sqrt{2}} − \sqrt{2}.
Solution.

  1. The key is that 4+23=(a+b3)24 + 2\sqrt{3} = \p{a + b\sqrt{3}}^2 for some a,b∈Ra, b \in \R. This isn't too surprising--we saw in Exercise 2.5 that (3+2)2\p{3 + \sqrt{2}}^2 is also in the form c+d2c + d\sqrt{2}. The only problem is figuring out what a,ba, b should be, which we do by working backwards and then checking that our choices of a,ba, b work. This would be considered scratchwork:

    (a+b3)2=4+23  ⟹  a2+3b2+2ab3=4+23.\p{a + b\sqrt{3}}^2 = 4 + 2\sqrt{3} \implies a^2 + 3b^2 + 2ab\sqrt{3} = 4 + 2\sqrt{3}.

    So we need a2+3b2=4a^2 + 3b^2 = 4 and 2ab=22ab = 2. This system has two solutions: (a,b)=(1,1)\p{a, b} = \p{1, 1} and (a,b)=(−1,−1)\p{a, b} = \p{-1, -1}. What this calculation tells us is that if 4+23=(a+b3)24 + 2\sqrt{3} = \p{a + b\sqrt{3}}^2, then the only possible way this could happen is if (a,b)=(1,1)\p{a, b} = \p{1, 1} or (a,b)=(−1,−1)\p{a, b} = \p{-1, -1}. It doesn't guarantee that this actually does happen; just that this is the only possibility. To show that this is possible, we just have to check manually that one of them works. We check (a,b)=(1,1)\p{a, b} = \p{1, 1}:

    (1+3)2=1+23+3=4+23,\p{1 + \sqrt{3}}^2 = 1 + 2\sqrt{3} + 3 = 4 + 2\sqrt{3},

    so it thankfully does work. This is where the scratchwork ends, i.e., this is roughly what you should have done to figure out how to write down the proof. Now you can write down the proof:

    Notice that 4+23=(1+3)24 + 2\sqrt{3} = \p{1 + \sqrt{3}}^2. Then

    4+23−3=(1+3)2−3=1+3−3=1∈Q.\sqrt{4 + 2\sqrt{3}} − \sqrt{3} = \sqrt{\p{1 + \sqrt{3}}^2} - \sqrt{3} = 1 + \sqrt{3} - \sqrt{3} = 1 \in \Q.

  2. This is exactly the same as in (1), except 6+42−2=2\sqrt{6 + 4\sqrt{2}} − \sqrt{2} = 2 instead.

Common Mistakes

The most common mistake I saw was trying to apply the rational roots theorem. The argument boils down to this:

Let x=4+23−3x = \sqrt{4 + 2\sqrt{3}} − \sqrt{3}. Then

x4−14x2+24x−11=0.x^4 - 14x^2 + 24x - 11 = 0.

Notice that 11 is a rational root of this polynomial. Therefore, xx must be rational.

The issue with this argument is that the polynomial p(a)=a4−14a2+24a−11p\p{a} = a^4 - 14a^2 + 24a - 11 has three roots other than 11, so knowing that p(x)=0p\p{x} = 0 only tells us that it's possible that x=1x = 1, but makes no guarantees. In other words, the rational roots theorem only helps us figure out the rational roots of pp, but tells us nothing about xx.
Exercise 1.

In Exercise 2.7, I showed that (a,b)=(1,1)\p{a, b} = \p{1, 1}. Show that (a,b)=(−1,−1)\p{a, b} = \p{-1, -1} also works. (Hint: (−1)2=1\sqrt{\p{-1}^2} = 1 and is not −1-1.)