1.2.1 exercises

1. We can modify the idea of the proof by mathematical induction, by first proving P(0) and P(1) then continuing as normal. We can also do, P(0) then assume true for 1, 2, …, n to then prove n + 1

2. The formula is not defined for n = 1 as $\frac{1}{(n-1) \times n}$ will be $\frac{1}{0 \times 1}$ which is undefined. Because the iteration is not defined, (when we hav 1…0 do we do just 1 or just 0

If we are to do induction, we have to start at n = 2, but. $\frac{1}{1 \times 2} \stackrel{!}{=} \frac{3}{2} - \frac{1}{2}$ $\text{ L.H.S } = \frac{1}{2}$ but R.H.S  = 1 CONTRADICTION.

4. Recall, $\phi = \frac{1 + \sqrt{5} }{2}$

W.T.S ϕ^n − 2 ≤ F_n where F_n is the nth term in the fibonnaci sequence.

base case

For n = 1, F₁ = 1 and $\phi^{1-2} = \frac{2}{1 + \sqrt{5} }$ We know that the square root function is monotonic for numbers greater than 1, and $\sqrt{4} = 2$,so $1+ \sqrt{5} > 1 + 2 = 3$.  ⟹ ϕ⁻¹ < 1

For n = 2, F₂ = 1 and ϕ⁰ = 1 and so we havee ϕ⁰ ≤ F₂

For n = 3, F₃ = 2 and $\phi^{1} = \frac{1 + \sqrt{5} }{2} \approx 1.618$ and so we have ϕ¹ ≤ F₃

For n = 4, F₄ = 3 and ϕ² ≈ 2.618 and so we have ϕ² ≤ F₄

With foresight, the inductive step uses 2^n − 4 so I wanted to make sure that this doesn’t cause any issues and figured out 1 ≤ n ≤ 4 explicitly.

assume true for ∀j : 1 < j < n to prove true for n

F_n = F_n − 1 + F_n − 2

As we are dealing with all positive numbers, we have

 ⟹ ϕ^n − 3 + ϕ^n − 4 ≤ F_n.

We need to show ϕ^n − 2 ≤ ϕ^n − 3 + ϕ^n − 4.

Plug in the formula values. $$\text{ LHS } = \frac{\left( 1 + \sqrt{5} \right)^{n-2} }{2^{n-2}}$$

$$\text{ RHS } = \frac{\left( 1 + \sqrt{5} \right)^{n-3} }{2^{n-3}} + \frac{\left( 1 + \sqrt{5} \right)^{n-4} }{2^{n-4}}$$

$$= \frac{\left( 1 + \sqrt{5} \right)^{n-3} }{2^{n-3}} + \frac{2 \times \left( 1 + \sqrt{5} \right)^{n-4} }{2^{n-3}}$$

$$= \frac{\left( 1 + \sqrt{5} \right)^{n-3} + 2 \times \left( 1 + \sqrt{5} \right)^{n-4} }{2^{n-3}}$$

$$= \frac{2 \times \left( 1 + \sqrt{5} \right)^{n-3} + 4 \times \left( 1 + \sqrt{5} \right)^{n-4} }{2^{n-2}}$$

We only need to compare numerators, we WTS, $\left( 1 + \sqrt{5} \right)^{n-2} \le 2 \times \left( 1 + \sqrt{5} \right)^{n-3} + 4 \times \left( 1 + \sqrt{5} \right)^{n-4}$

$u `:=` 1 + \sqrt{5}$

u^n − 2 ≤ 2u^n − 3 + 4u^n − 4  ⟹ u²u^n − 4 ≤ 2u^n − 4u + 4u^n − 4  ⟹ u² ≤ 2u + 4 We can now plug in the values.

$\implies (1 + sqrt{5})^2 = 6 + 2\sqrt{5} \le 2(1 + sqrt{5}) + 4 = 6 + 2\sqrt{5} \square$

5. prove that every positve integer  > 2 can be written as a product of primes.

base case

n = 2 we are done as 2 is a prime.

assume true for 2 ≤ j < n to prove true for n

For sake of contradiction, suppose that n cannot be expressed as a product of primes. Why would this be the case? n must have at least 2 factors, as it is greater than 1, and n itself is a factor of n. But it must have more factors, as if it only had 2 factors than n is prime and we are done, we have a expression of a product of primes.

If it had a factor aⁱ = n, i > 1, We must have that a < n, and therefore by our assumption a can be expressed as a product of primes. so n = a = p₁…p_n. In fact, any factor has the property of being less than n and therefore by our induction step we know it is expressed as a factor of primes. ▫

Wts if a^′m + b^′n = c, am + bn = d hold before step 4 on the euclidean_algorithm, then they hold after.

Set c ← d,

We have d = a^′m + b^′n

d ← r, We have am + bn = r

t ← a^′, a^′ ← a, We have d = am + b^′n

a ← t − qa, t ← b^′, b^′ ← b, b ← t − qb Go to step 2.

We have d = a^′m + b^′n

am + bn = d and am + bn = r

base case

F₁ = 1² = 1 F₂ = 2² − 1² = 3 = F₁ + 2 F₃ = 3² − 2² + 1² = 6 = F₂ + 3 F₄ = 4² − 3² + 2² − 1² = 10 = F₃ + 4 F₅ = 5² − 4² + 3² − 2² + 1² = 15 = F₄ + 5

wts if valid for F_k : 1 < k < n ⟹ F_k + 1 = F_k + k + 1

F_k + 1 = (k + 1)² − F_k  = k² + 2k + 1 − F_k F_k = F_k − 1 + k tautologically  ⟹ F_k + 1 = k² + 2k + 1 − F_k − 1 − k F_k = k² − F_k − 1  ⟹ F_k + 1 = F_k + k + 1

8. prove Nicomachus theorem by induction.

1. summation

base case

1³ = 1 2³ = 3 + 5 3³ = 7 + 9 + 11 4³ = 13 + 15 + 17 + 19 etc.

scratch

f(k) = k * (k − 1) + 1 + k * (k − 1) + 3 + k * (k − 1) + 4

(k + 1)²(k) + k + 1 + k(2k + 1)

$f(k+1) = $  = k³ + 3k² + 3k + 1

wts if valid for F_k + 1 : 1 < k + 1 < n ⟹ (k + 2)³ = (k + 1)³ + 3(k + 1)² + 3(k + 1) + 1

RHS (k + 2)³ = (k² + 4k + 4)(k + 2)  = k³ + 4k² + 4k + 2k² + 8k + 8 k³ + 6k² + 12k + 8

LHS (k² + 2k + 1)(k + 1) + 3(k² + 2k + 1) + 3k + 3 + 1  = k³ + 2k² + k + k² + 2k + 1 + 3k² + 6k + 3 + 3k + 3 + 1  = k³ + 6k² + 12k + 8

b)

base case

1³ = 1² 1³ + 2³ = 9 = (1 + 2)² 1³ + 2³ + 3³ = 36 = (1 + 2 + 3)²

We assume the that the formula $\sum _{i=1}^{n} i^3 = \left( \sum _{i=1}^{n} i \right)^2$ holds true.

assume true for n = a − 1 to show true for n = a

$$\sum _{i=1}^{n} i^3 = \sum _{i=0}^{n-1}i^3 + 3i^2 + 3i + 1$$ $$= (\sum _{i=1}^{n-1} i)^2 + 3 \sum _{i=1}^{n-1} i^2 + 3 \sum _{i=1}^{n-1} i + n$$ $$\left( \frac{1}{2}(n)(n-1) \right) ^2 + 3 \frac{1}{6}(n-1)(n)(2(n-1)+1) + 3 \frac{1}{2}(n-1)(n) + n$$ $$= \frac{1}{4}n^2(n^2 - 2n + 1) + \frac{1}{2}(n^2 - n)( 2n -1) + \frac{3}{2}(n^2 -n) + n$$ $$\frac{1}{4} (n^{4} - 2n^3 + n^2) + \frac{1}{2}(2n^3 - n^2 - 2n^2 + n) + \frac{3}{2}(n^2 - n) + n$$ $$\frac{1}{4} (n^{4} - 2n^3 + n^2 + 2(2n^3 - n^2 - 2n^2 + n) + 6(n^2 - n) + 4n)$$ $$\frac{1}{4} (n^{4} - 2n^3 + n^2 + 4n^3 - 2n^2 - 4n^2 + 2n + 6n^2 - 6n + 4n)$$ $$\frac{1}{4} (n^{4} + 2n^3 + n^2)$$

Compare to $$\left( \frac{1}{4}a^2(a+1)^2 \right)$$ $$\frac{1}{4}a^2 (a^2 + 2a + 1)$$ $$\frac{1}{4} (a^{4} + 2a^3 + a^2)$$

Which is in the form we wanted ▫

9. Prove by induction that if 0 < a < 1 then (1 − a)ⁿ ≥ 1 − na∀n ∈ ℤ

We have to prove this for integers positive and negative. Let’s start with the positive integers.

n = 0 ⟹ 1 ≥ 1 n = 1 ⟹ (1 − a) ≥ 1 − a n = 2 ⟹ (1 − a)² = 1 − 2a + a² ≥ 1 − 2a

Assume that for n = k ⟹ (1 − a)^k ≥ 1 − ka to show true for n = k + 1 WTS. (1 − a)^k + 1 ≥ 1 − (k + 1)a LHS. (1 − a)^k + 1 = (1 − a)^k(1 − a) RHS. 1 − (k + 1)a = 1 − ka − a

By our inductive step, we know that (1 − a)^k ≥ (1 − ka) so we WTS, $$(1-a)^{k}(1-a) \ge (1-ka)(1 - \frac{a}{1-ka})$$ We cancel out the known terms $$\iff(1-a) \ge (1-\frac{a}{1-ka})$$ $$\iff -a \ge -\frac{a}{1-ka}$$ $$\iff 1 \le \frac{1}{1-ka}$$  ⇔ 1 − ka ≤ 1  ⇔ −ka ≤ 0 which is part of our assumption of a hence true.

Inductive step. Assume true that for n = −k ⟹ (1 − a)^−k ≥ 1 + ka to show true for n = −k − 1

WTS. $$\frac{1}{(1-a)^{k}} \times \frac{1}{1-a} \ge!! 1 -(-k-1)a = 1 + ka + a$$

RHS $$1 + ka + a = (1+ka) (1+ \frac{a}{1+ka})$$

WTS $$\frac{1}{1-a} \ge 1 + \frac{a}{1 +ka}$$ $$\iff \frac{1}{1-a} \ge \frac{1 + ka + a}{1 +ka}$$  ⇔ 1 + ka ≥ (1 + ka + a)(1 − a) = 1 + ka − ka² − a²  ⇔ 0 ≥ −ka² − a² which is true.

10. Prove by induction that if n ≥ 10 then 2ⁿ > n³

TODO readable and potentially wrong in proof We need to look up nature of cubic equations.

base case

if n = 10 then 2¹⁰ = 1024 and n³ = 1000.

assume true for n ≤ k to prove n = k + 1.

2^k + 1 = 2^k2¹. We know 2^k > k³ so this implies 2^k2¹ > 2k³

Suffice to show 2(k)³ > (k + 1)³. (k + 1)³ = (k + 1)(k² + 2k + 1)  = (k³ + 2k² + k + k² + 2k + 1)  = k³ + 3k² + 3k + 1

2k³ − k³ − 3k² − 3k − 1 $f(k) `:=` k^3 - 3k^2 - 3k - 1$

$\frac{d}{d k} f = 3k^2 - 6k - 3$ wts that the function is increasing when k ≥ 10

consider $g(k) `:=` k^2 - 2k - 1$

$\frac{d}{d k} g(k) = 2k - 2$ which is increasing for k > 10

 ⟹ g(k) is increasing, ⟹ f(k) is increasing, hence the our original statement is must be true, ▫

backlinks

• index_of_files.pd
• taocp_exercises