how to prove it - ch6, sec6.1(Proof by mathematical Induction) ex

This scetion introduces another proof technique, called Mathematical Induction, to prove the statements P(n) where n is arbitrary natural number. That is n = {0, 1, 2, 3, 4, ...}. Here is how you do it.

To Prove a goal of the form $\forall n \in N P(n)$:
First prove P(0), and then prove $\forall n \in N (P(n) \rightarrow P(n+1))$. The first of these proofs is sometimes called the *base case* and the second the *induction step*. Premise of the induction step is called the *induction hypothesis*.

Form of the final proof:
Base case: [Proof of P(0) goaes here]
Induction Step: [Proof of $\forall n \in N (P(n) \rightarrow P(n+1))$ goes here]

Why Mathematical Induction works?
Well, certainly P(0) is true because we prove it in the base case. Also, we prove that $\forall n \in N (P(n) \rightarrow P(n+1))$. So P(0) -> P(1). Then P(1) -> P(2). Then P(2) -> P(3). It goes on. Continuing in this way, you should be able to see that by repeatedly applying the induction step you can show that P(n) must be true for every natural number.

A small variation in the problem might be to prove the goal of the form, for all natural number n $\geq$ k, k is a natural number, P(n). Then simply the base case becomes n = k instead of n = 0.

=============================================================================================

Ex-1:
Base case: For n = 0, both sides are 0 and hence same.

Induction Step:
Let n be an arbitrary natural number s.t. 0 + 1 + 2 + ... + n = $\frac{n(n+1)}{2}$

Now, 0 + 1 + 2 + ... + n + (n+1)
= $\frac{n(n+1)}{2}$ + (n+1)
= $\frac{(n+2)(n+1)}{2}$


Ex-2: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^2 + 1^2 + 2^2 + ... + n^2 = \frac{(n(n+1)(2n+1)}{6}$

Now, $0^2 + 1^2 + 2^2 + ... + n^2 + (n+1)^2$
= $\frac{(n(n+1)(2n+1)}{6} + (n+1)^2$
= $\frac{(n+1)(n+2)(2n+3)}{6}$


Ex-3: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^3 + 1^3 + 2^3 + ... + n^3 = [\frac{(n(n+1)}{2}]^2$

Now, $0^3 + 1^3 + 2^3 + ... + n^3 + (n+1)^3$
= $[\frac{(n(n+1)}{2}]^2 + (n+1)^3$
= $\frac{(n+1)^2(n^2 + 4(n+1))}{4}$
= $[\frac{(n+1)(n+2)}{2}]^2$


Ex-4: Scratchwork:
P(1) = 1, P(2) = 4, P(3) = 9, P(4) = 16...

its easy to guess that P(n) = $n^2$. Let us try to prove it now.

Formal Proof:

Base case: For n = 1, LHS = 1 and RHS = $1^2$ = 1. cleary LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $n \geq 1$ and 1 + 3 + 5 ... + (2n-1) = $n^2$

Now, 1 + 3 + 5 + ... + (2n-1) + (2n+1)
= $n^2 + 2n + 1$
= $(n+1)^2$


Ex-5: Base case: For n = 0, both sides are 0 and hence same

Induction step:
Let n be arbitrary natural number s.t. 0.1 + 1.2 + 2.3 + ... + n(n+1) = $\frac{n(n+1)(n+2)}{3}$

Now, 0.1 + 1.2 + 2.3 + ... + n(n+1) + (n+1)(n+2)
= $\frac{n(n+1)(n+2)}{3}$ + (n+1)(n+2)
= $\frac{(n+1)(n+2)(n+3)}{3}$


Ex-6: Scratchwork: My guess using results of ex1,5 is $\frac{n(n+1)(n+2)(n+3)}{4}$
Formal Proof:

Base case: For n = 0, both sides are 0 and hence same.

Induction step:
Let n be arbitrary natural number s.t. 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) = $\frac{n(n+1)(n+2)(n+3)}{4}$

Now, 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) + (n+1)(n+2)(n+3)
= $\frac{n(n+1)(n+2)(n+3)}{4}$ + (n+1)(n+2)(n+3)
= $\frac{(n+1)(n+2)(n+3)(n+4)}{4}$


Ex-7: Guess is $\frac{3^{n+1} - 1}{2}$

Base case: For n = 10, LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $3^0 + 3^1 + 3^2 + ... + 3^n = \frac{3^{n+1} - 1}{2}$

$3^0 + 3^1 + 3^2 + ... + 3^n + 3^{n+1}$
= $\frac{3^{n+1} - 1}{2} + 3^{n+1}$
= $\frac{3^{n+2} - 1}{2}$


Ex-8: Base case: For n = 1, LHS = 1 - 1/2 = 1/2 and RHS = 1/2. clearly both sides are equal

Induction Step:
Let n be arbitrary natural number s.t. $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + ... + \frac{1}{2n-1} - \frac{1}{2n} = \frac{1}{n+1} + \frac{1}{n+2} + ... + \frac{1}{2n}$

Now, $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + ... + \frac{1}{2n-1} - \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2}$
= $\frac{1}{n+1} + \frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2}$
= $\frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2} + \frac{1}{n+1}$
= $\frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} + \frac{1}{2n+2}$


Ex-9:
(a) Base case: For n = 0, clearly 2 divides $0^2 + 0 = 0$
Induction Step:
Let n be arbitrary natural number s.t. $2 | n^2 + n$. Then we can choose some integer k s.t. $n^2 + n = 2k$

$(n+1)^2 + (n+1)$
= $n^2 + 2n + 1 + n + 1$
= $(n^2 + n) + 2(n+1)$
= 2(k + n + 1)

clearly, $2 | [(n+1)^2 + (n+1)]$

(b) Base case: For n = 0, clearly 6 divides $0^3 - 0 = 0$
Induction Step:
Let n be arbitrary natural number s.t. $6|(n^3 - n)$. Then we can choose some integer k s.t. $n^3 - n = 6k$

Now, $(n+1)^3 - (n+1)$
= $n^3 + 1 + 3n^2 + 3n - n - 1$
= $(n^3 - n) + 3(n^2 + n)$

In Part(a) we prove that $n^2 + n$ is always divisible by 2. so we can choose some integer l s.t. $n^2 + n = 2l$

So, $(n+1)^3 - (n+1)$
= $(n^3 - n) + 3(n^2 + n)$
= 6k + 3(2l)
= 6(k+l)

clearly 6 divides $(n+1)^3 - (n+1)$


Ex-10: Base case: For n = 0, clearly 64 divides $9^0 - 8(0) - 1 = 0$
Induction step:
Let n be arbitrary natural number s.t. 64 divides $9^n - 8n - 1$. Then we can choose some integer k s.t. $9^n - 8n - 1 = 64k$

Now, $9^{n+1} - 8(n+1) - 1$
= $9.9^n - 8n -9$
= $9(9^n - 8n - 1) + 64n$
= 9(64k) + 64n$
= 64(9k + 1)

clearly 64 divides $9^{n+1} - 8(n+1) - 1$


Ex-11: Base case: For n = 0, clearly 9 divides $4^0 + 6(0) - 1 = 0$
Induction step:
Let n be arbitrary natural number s.t. 9 divides $4^n + 6n - 1$. Then we can choose some integer k s.t. $4^n + 6n - 1 = 9k$

Now, $4^{n+1} + 6(n+1) - 1$
= $4.4^n + 6n + 6 - 1$
= $4(4^n + 6n - 1) - 18n + 9$
= $4(9k) - 9(2n - 1)$
= $9(4k - 2n + 1)$

clearly 9 divides $4^{n+1} + 6(n+1) - 1$


Ex-12: Base case: For n = 0, clearly (a-b) divides $(a^0 - b^0) = 0$
Induction step:
Let n be arbitrary natural number s.t. (a-b) divides $a^n - b^n$. Then we can choose some integer k s.t. $a^n - b^n = (a-b)k$

Now, $a^{n+1} - b^{n+1}$
= $a(a^n - b^n) + ab^n - b^{n+1}$
= $a(a^n - b^n) + b^n(a-b)$
= $(a-b)(ka + b^n)$


clearly (a-b) divides $a^{n+1} - b^{n+1}$


Ex-13: Base case: For n = 0, clearly (a+b) divides $a^{2(0) + 1} + b^{2(0) + 1} = (a+b)$
Induction step:
Let n be arbitrary natural number s.t. (a+b) divides $a^{2n+1} + b^{2n+1}$

Now, $a^{2(n+1)+1} + b^{2(n+1)+1}$
= $a^{2n+3} + b^{2n+3}$
= $a^2(a^{2n+1} + b^{2n+1}) - a^2b^{2n+1} + b^{2n+3}$
= $a^2(a+b)k - b^{2n+1}(a^2 - b^2)$
= $(a+b)(a^2k - b^{2n+1}(a-b))$

clearly (a+b) divides $a^{2(n+1)+1} + b^{2(n+1)+1}$


Ex-14: Base case: For n = 10, $2^{10} = 1024 > 10^3 = 1000$
Induction step:
Let n be arbitrary natural number s.t. $2^n > 10^n$

Now, $2^{n+1}$
= $2.2^n$
> $2n^3$ = $n^3 + n^3$ = $n^3 + 10n^2$ (bacause $n \geq 10$)
= $n^3 + 3n^2 + 3n^2 + n^2$
> $n^3 + 3n^2 + 3n + 1$ = $(n+1)^3$

clearly $2^{n+1} > (n+1)^3$


Ex-15: Base case: For n = 0, clearly $0 \equiv 0 (mod 3)$
Inductive step:
Let n be a arbitrary natural number s.t. $n \equiv 0 (mod 3)$ or $n \equiv 1 (mod 3)$ or $n \equiv 2 (mod 3)$. Let us consider all the possible cases for (n+1)

Case#1: $n \equiv 0 (mod 3)$
Then we can choose some integer k s.t. n = 3k. Then (n + 1) = 3k + 1. Then $(n+1) - 1 = 3k$. Thus $(n+1) \equiv 1 (mod 3)$

Case#2: $n \equiv 1 (mod 3)$
Then we can choose some integer k s.t. (n-1) = 3k. Then (n+1) = 3k+2. Then $(n+1) - 2 = 3k$. Thus $(n+1) \equiv 2 (mod 3)$

Case#3: $n \equiv 2 (mod 3)$
Then we can choose some integer k s.t. (n-2) = 3k. Then (n+1) = 3k+3. Then $(n+1) - 0 = 3(k+1)$. Thus $(n+1) \equiv 0 (mod 3)$

Thus $(n+1) \equiv 0 (mod 3)$ or $(n+1) \equiv 1 (mod 3)$ or $(n+1) \equiv 2 (mod 3)$


Ex-16: Base case: For n = 1. LHS = $2.2^1$ = 4, RHS = $(1)2^{1+1} = 4$. clearly LHS = RHS
Induction Step:
Let n be arbitrary natural number s.t. $2.2^1 + 3.2^2 + 4.2^3 + ... + (n+1)2^n = n2^{n+1}$

Now, $2.2^1 + 3.2^2 + 4.2^3 + ... + (n+1)2^n + (n+2)2^{n+1}$
= $n2^{n+1} + (n+2)2^{n+1}$
= $n2^{n+1} + n2^{n+1} + 2^{n+2}$
= $n2^{n+2} + 2^{n+2}$
= $(n+1)2^{n+2}$


Ex-17:
(a) Base case is not proved.

(b) Scratchwork:
I could not actually guess it. So I solved it. However, after finding the answer, it seems it was so easy to guess :)

P(n) = $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n$
3P(n) = $1.3^1 + 3.3^2 + ... + (2n-1)3^n + (2n+1)3^{n+1}$

P(n) - 3P(n) = $1.3^0 + 2.3^1 + 2.3^2 + .... + 2.3^n - (2n+1)3^{n+1}$
P(n) - 3P(n) = $-1.3^0 + 2(3^0 + 3^1 + 3^2 + ... + 3^n) - (2n+1)3^{n+1}$ ,now use result of ex-7
P(n) - 3P(n) = $-1 + 2\frac{3^{n+1} - 1}{2} - (2n+1)3^{n+1}$
2P(n) = $1 - 2\frac{3^{n+1} - 1}{2} + (2n+1)3^{n+1}$
2P(n) = $1 - 3^{n+1} + 1 + (2n+1)3^{n+1}$
2P(n) = $2 + 2n3^{n+1}$
P(n) = $1 + n3^{n+1}$

So, $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n = 1 + n3^{n+1}$

Formal Proof:

Base case: For n = 0. LHS = $1.3^0$ = 1, RHS = $1 + (0)3^{0+1}$ = 1 + 0 = 1

Induction step:
Let n be arbitrary natural number s.t. $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n = 1 + n3^{n+1}$

Now, $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n + (2n+3)3^{n+1}$
= $1 + n3^{n+1} + (2n+3)3^{n+1}$
= $1 + n3^{n+1} + 2n3^{n+1} + 3.3^{n+1}$
= $1 + 3n3^{n+1} + 3^{n+2}$
= $1 + (n+1)3^{n+2}$


Ex-18: Note that even/odd is defined to natural numbers $\geq$ 1
Base case: for n = 1, clearly 1 is odd and $a^1 = a < 0$

Induction step:

Let n be an arbitrary natural number. if n is even then $a^n > 0$ or if n is odd then $a^n < 0$. Let us consider both the cases

Case#1: n is even and $a^n > 0$
(n+1) is odd. And $a^{n+1}$ = $a.a^n$. Since a is negative and $a^n$ is positive, so $a^{n+1} < 0$

Case#2: n is odd and $a^n < 0$
(n+1) is even. And $a^{n+1}$ = $a.a^n$. Since a is negative and also $a^n$ is negative, so $a^{n+1} > 0$


Ex-19:
(a) Base case: For n = 1, 0 < a < b
Induction step:
Let n be arbitrary natural number greater thant or equal to 1 s.t. $0 < a^n < b^n$.

clearly, $0 < a^{n+1}$.

Now, $b^{n+1} = bb^n > ba^n > aa^n = a^{n+1}$
Thus, $0 < a^{n+1} < b^{n+1}$

(b) TODO

(c) We'll prove the inequality directly.
inequality to prove is, $ab^n + ba^n < a^{n+1} + b^{n+1}$. it can rewritten as $a^{n+1} + b^{n+1} - ab^n - ba^n > 0$

Now $a^{n+1} + b^{n+1} - ab^n - ba^n$
= $a^{n+1} - ab^n + b^{n+1} - ba^n$
= $a(a^n - b^n) - b(a^n - b^n)$
= $(a-b)(a^n - b^n)$
= $(b-a)(b^n - a^n)$

from part(a), $a^n < b^n$
=> $(b^n - a^n) > 0$

also (b-a) > 0

Hence $a^{n+1} + b^{n+1} - ab^n - ba^n$ = $(b-a)(b^n - a^n)$ > 0

(d) Base case: For n = 2,
$(\frac{a+b}{2})^2 = \frac{a^2 + b^2}{4} + \frac{2ab}{4}$

In part(c), putting n = 1 gives
$ab + ba < a^2 + b^2$
=> $2ab < a^2 + b^2$

So, $(\frac{a+b}{2})^2$
= $\frac{a^2 + b^2}{4} + \frac{2ab}{4}$
< $\frac{a^2 + b^2}{4} + \frac{a^2 + b^2}{4}$ = $\frac{a^2 + b^2}{2}$

Induction step:
Let n be arbitrary natural number greater than or equal to 2 s.t. $(\frac{a+b}{2})^n < \frac{a^n + b^n}{2}$

Multiplying both sides of above inequality with $\frac{a+b}{2}$, we get

$(\frac{a+b}{2})^{n+1} < \frac{a^n + b^n}{2}.\frac{a+b}{2}$
=> $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4}$

from part(c), $ab^n + ba^n < a^{n+1} + b^{n+1}$
so, $\frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4} < \frac{2(a^{n+1} + b^{n+1})}{4} = \frac{a^{n+1} + b^{n+1}}{2}$

Hence, $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1}}{2}$