how to prove it - ch6, sec6.3(Recursion) ex

This section introduces recursion and shows how it relates to mathematical induction. Also, in recursive formulae, since we can easily relate f(n+1) to f(n) so they are usually proved with mathematical induction. For similar reason, proofs involving ∑ are also easily done by induction.

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

Ex-1: Scratchwork:
P(1) = 1/2
P(2) = 2/3
P(3) = 3/4

It is easy enough to guess that P(n) = $\frac{n}{n+1}$

Formal Proof:

Base case: n = 1, $\frac{1}{1(1+1)}$ = $\frac{1}{2}$

Induction step:

Let, $\sum_{i=1}^{n} \frac{1}{i(i+1)}$.

Now, $\sum_{i=1}^{n+1} \frac{1}{i(i+1)}$
= $\sum_{i=1}^{n} \frac{1}{i(i+1)}$ + $\frac{1}{(n+1)(n+2)}$
= $\frac{n}{n+1} + \frac{1}{(n+1)(n+2)}$
= $\frac{1}{n+1}(n + \frac{1}{n+2})$
= $\frac{1}{n+1}(\frac{(n+1)^2}{n+2})$
= $\frac{n+1}{n+2}$


Ex-2: Base case: For n = 1,
LHS = $\frac{1}{1(1+1)(1+2)}$ = $\frac{1}{6}$
RHS = $\frac{1^2 + 3(1)}{4(1+1)(1+2)}$ = $\frac{4}{4.2.3}$ = $\frac{1}{6}$

clearly, LHS = RHS

Induction step:

Let, $\sum_{i=1}^{n} \frac{1}{i(i+1)(i+2)} = \frac{n^2 + 3n}{4(n+1)(n+2)}$

Now, $\sum_{i=1}^{n+1} \frac{1}{i(i+1)(i+2)}$
= $\sum_{i=1}^{n} \frac{1}{i(i+1)(i+2)} + \frac{1}{(n+1)(n+2)(n+3)}$
= $\frac{n^2 + 3n}{4(n+1)(n+2)} + \frac{1}{(n+1)(n+2)(n+3)}$
= $\frac{1}{(n+1)(n+2)}(\frac{n^2 + 3n}{4} + \frac{1}{n+3})$
= $\frac{(n^3 + 5n^2 + 4n) + (n^2 + 5n + 4)}{4(n+1)(n+2)(n+3)}$
= $\frac{(n^2 + 5n + 4)n + (n^2 + 5n + 4)}{4(n+1)(n+2)(n+3)}$
= $\frac{(n^2 + 5n + 4)(n+1)}{4(n+1)(n+2)(n+3)}$
= $\frac{n^2 + 5n + 4}{4(n+2)(n+3)}$
= $\frac{(n+1)^2 + 3(n+1)}{4(n+2)(n+3)}$


Ex-3: Base case: For n = 2

LHS = $\frac{1}{(2-1)(2+1)}$ = $\frac{1}{3}$
RHS = $\frac{3.2^2 - 2 - 2}{4.2(2+1)}$ = $\frac{12 - 4}{4.2.3}$ = $\frac{8}{4.2.3}$ = $\frac{1}{3}$

Induction step:

Let, $\sum_{i=2}^{n} \frac{1}{(i-1)(i+1)} = \frac{3n^2 - n - 2}{4n(n+1)}$

Now, $\sum_{i=2}^{n+1} \frac{1}{(i-1)(i+1)}$
= $\sum_{i=2}^{n} \frac{1}{(i-1)(i+1)} + \frac{1}{n(n+2)}$
= $\frac{3n^2 - n - 2}{4n(n+1)} + \frac{1}{n(n+2)}$
= $\frac{1}{n}[\frac{3n^2 - n - 2}{4(n+1)} + \frac{1}{(n+2)}]$
= $\frac{1}{n}[\frac{(3n^2 - n - 2)(n+2) + 4(n+1)}{4(n+1)(n+2)}]$
= $\frac{1}{n}[\frac{3n^3 - n^2 - 2n + 6n^2 - 2n - 4 + 4n + 4}{4(n+1)(n+2)}]$
= $\frac{1}{n}[\frac{3n^3 + 5n^2}{4(n+1)(n+2)}]$
= $\frac{3n^2 + 5n}{4(n+1)(n+2)}$
= $\frac{3(n^2 + 2n + 1) - 6n - 3 + 5n}{4(n+1)(n+2)}$
= $\frac{3(n+1)^2 - (n+1) - 2}{4(n+1)(n+2)}$


Ex-4: Base case: For n = 0;

LHS = $(2(0) + 1)^2$ = 1
RHS = $\frac{(0+1)(2.0+1)(2.0+3)}{3}$ = $\frac{(1)(1)(3)}{3}$ = 1

clearly, LHS = RHS

Induction step:

Let, $\sum_{i=0}^{n} (2i + 1)^2 = \frac{(n+1)(2n+1)(2n+3)}{3}$

Now, $\sum_{i=0}^{n+1} (2i + 1)^2$
= $\sum_{i=0}^{n} (2i + 1)^2 + (2(n+1) + 1)^2$
= $\frac{(n+1)(2n+1)(2n+3)}{3} + (2n+3)^2$
= $(2n+3)[\frac{(n+1)(2n+1)}{3} + (2n+3)]$
= $(2n+3)[\frac{(2n^2 + 3n + 1) + (6n+9)}{3}]$
= $(2n+3)[\frac{2n^2 + 9n + 10}{3}]$
= $(2n+3)[\frac{2n^2 + 4n + 5n + 10}{3}]$
= $(2n+3)[\frac{(n+2)(2n+5)}{3}]$
= $\frac{(n+2)(2n+3)(2n+5)}{3}$


Ex-5: Base case: For n = 0

LHS = $r^0$ = 1
RHS = $\frac{r^{(0+1)} - 1}{r-1}$ = $\frac{r-1}{r-1}$ = 1

Induction step:

Let, $\sum_{i=0}^{n} r^i = \frac{r^{(n+1)} - 1}{r-1}$

Now, $\sum_{i=0}^{n+1} r^i$
= $\sum_{i=0}^{n} r^i + r^{(n+1)}$
= $\frac{r^{(n+1)} - 1}{r-1} + r^{(n+1)}$
= $\frac{r^{(n+1)} - 1 + r^{(n+2)} - r^{(n+1)}}{r-1}$
= $\frac{r^{(n+2)} - 1}{r-1}$


Ex-6: Base case: For n = 1

LHS = $\frac{1}{1^2}$ = 1
RHS = $2 - \frac{1}{1}$ = 1

clearly, LHS $\leq$ RHS

Induction step:

Let, $\sum_{i=1}^{n} \frac{1}{i^2} \leq 2 - \frac{1}{n}$

Now, $\sum_{i=1}^{n+1} \frac{1}{i^2}$
= $\sum_{i=1}^{n} \frac{1}{i^2} + \frac{1}{(n+1)^2}$
$\leq (2 - \frac{1}{n}) + \frac{1}{(n+1)^2}$
= $(2 - \frac{1}{n+1}) + \frac{1}{n+1} - \frac{1}{n} + \frac{1}{(n+1)^2}$
= $(2 - \frac{1}{n+1}) + \frac{(n^2 + n) - (n^2 + 1 + 2n) + n}{n(n+1)^2}$
= $(2 - \frac{1}{n+1}) - \frac{1}{n(n+1)^2}$
$\leq (2 - \frac{1}{n+1})$


Ex-7:
(a) Base case: for n = 0

LHS = RHS = $a_0 + b_0$

Induction step:

Let $\sum_{i=0}^{n} (a_i + b_i) = \sum_{i=0}^{n} a_i + \sum_{i=0}^{n} b_i$

Now, $\sum_{i=0}^{n+1} (a_i + b_i)$
= $\sum_{i=0}^{n} (a_i + b_i) + (a_{n+1} + b_{n+1})$
= $\sum_{i=0}^{n} a_i + \sum_{i=0}^{n} b_i + (a_{n+1} + b_{n+1})$
= $(\sum_{i=0}^{n} a_i + a_{n+1}) + (\sum_{i=0}^{n} b_i + b_{n+1})$
= $\sum_{i=0}^{n+1} a_i + \sum_{i=0}^{n+1} b_i$

(b) Base case: for n = 0, LHS = RHS = $ca_0$

Induction step: Let $c\sum_{i=0}^{n} a_i = \sum_{i=0}^{n} (c.a_i)$

Now, $c\sum_{i=0}^{n+1} a_i$
= $c\sum_{i=0}^{n} a_i + c.a_{n+1}$
= $\sum_{i=0}^{n} (c.a_i) + (c.a_{n+1})$
= $\sum_{i=0}^{n+1} (c.a_i)$


Ex-8:
(a) We will let m be arbitrary natural number and prove that $\forall n \in N (n \geq m \rightarrow H_n - H_m \geq \frac{n-m}{n}$

Base case: For n = m
LHS = $H_m - H_m$ = 0 = $\frac{m - m}{m}$ = RHS

Induction step: Let n be arbitrary natural number greater than or equal to m and $H_n - H_m \geq \frac{n-m}{n}$

Now, $H_{n+1} - H_m$
= $(\sum_{i=1}^{n+1} \frac{1}{i}) - H_m$
= $(\sum_{i=1}^{n} \frac{1}{i} + \frac{1}{n+1}) - H_m$
= $(H_n + \frac{1}{n+1}) - H_m$
= $(H_n - H_m) + \frac{1}{n+1}$
$\geq \frac{n-m}{n} + \frac{1}{n+1}$
= $\frac{n^2 + n - mn - m + m}{m(n+1)}$
= $\frac{n}{m}.\frac{(n+1)-m}{n+1}$ (since n $\geq$ m, so $\frac{n}{m} \geq 1$)
$\geq \frac{(n+1)-m}{n+1}$

(b) Base case: For n = 0, LHS = $H_{2^0} = H_1 = 1 = 1 + \frac{0}{2} = 1$ = RHS

Induction step: Let $H_{2^n} \geq 1 + \frac{n}{2}$

Now, using part(a) $H_{2^{n+1}} - H_{2^n}$
$\geq \frac{2^{n+1} - 2^n}{2^{n+1}}$
= $\frac{2^n(2-1)}{2^{n+1}}$
= $\frac{1}{2}$
So, $H_{2^{n+1}} - H_{2^n} \geq \frac{1}{2}$
=> $H_{2^{n+1}} \geq H_{2^n} + \frac{1}{2}$
=> $H_{2^{n+1}} \geq 1 + \frac{n}{2} + \frac{1}{2}$
=> $H_{2^{n+1}} \geq 1 + \frac{n+1}{2}$


Ex-9: Base case: For n = 2

LHS = $\sum_{k=1}^{1} H_k = H_1 = 1$
RHS = $2(1 + \frac{1}{2}) - 2$ = 2 + 1 - 2 = 1

clearly, LHS = RHS

Induction step: Let $\sum_{k=1}^{n-1} H_k = nH_n - n$

Now, $\sum_{k=1}^{n} H_k$
= $(\sum_{k=1}^{n-1} H_k) + H_n$
= $nH_n - n + H_n$
= $(n+1)H_n - n$

Since $H_{n+1} = \sum_{i=1}^{n+1} \frac{1}{i} = \sum_{i=1}^{n} \frac{1}{i} + \frac{1}{n+1}$
=> $H_n = H_{n+1} - \frac{1}{n+1}$

Hence, $\sum_{k=1}^{n} H_k$
= $(n+1)H_n - n$
= $(n+1)(H_{n+1} - \frac{1}{n+1}) - n$
= $(n+1)H_{n+1} - (n+1)$


Ex-10: Scratchwork:
P(1) = 1 = 2! - 1
P(2) = 5 = 3! - 1
P(3) = 23 = 4! - 1
P(4) = 119 = 5! - 1

It is easy enough to guess that P(n) = (n+1)! - 1

Theorem: $\sum_{i=1}^{n} (i(i!))$ = (n+1)! - 1
Proof:

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

Induction step: Let $\sum_{i=1}^{n} (i(i!))$ = (n+1)! - 1

Now, $\sum_{i=1}^{n+1} (i(i!))$
= $\sum_{i=1}^{n} (i(i!))$ + (n+1).(n+1)!
= (n+1)! - 1 + (n+1).(n+1)!
= (1 + n + 1)(n+1)! - 1
= (n + 2)(n+1)! - 1
= (n+2)! - 1


Ex-11: Scratchwork:

P(0) = 0
P(1) = 1/2
P(2) = 5/6
P(3) = 23/24

My guess: P(n) = $\frac{(n+1)! - 1}{(n+1)!}$

Proof:

Base case: For n = 0, LHS = 0 = RHS

Induction step: Let $\sum_{i=0}^{n} \frac{i}{(i+1)!} = \frac{(n+1)! - 1}{(n+1)!}$

Now, $\sum_{i=0}^{n+1} \frac{i}{(i+1)!}$
= $\sum_{i=0}^{n} \frac{i}{(i+1)!} + \frac{(n+1)}{(n+2)!}$
= $\frac{(n+1)! - 1}{(n+1)!} + \frac{(n+1)}{(n+2)!}$
= $\frac{[(n+1)! - 1](n+2)}{(n+2)!} + \frac{(n+1)}{(n+2)!}$
= $\frac{1}{(n+2)!}[(n+2)! - (n+2) + (n+1)]$
= $\frac{(n+2)! - 1}{(n+2)!}$


Ex-12:
(a) Base case: n = 0, clearly $2^0$ = 1 > 0

Induction step:

Let, for an arbitrary natural number n s.t. n $\geq 1$, $2^n > n$

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

Thus, $2^{(n+1)} \geq (n+1)$

(b) Base case: n = 9, 9! = 362880 $\geq$ 262144 = $2^{18} = {(2^9)}^2$

Induction step: Let n be an arbitrary natural number s.t. n $\geq 9$ and $n! \geq {(2^n)}^2$

Now, (n+1)! = (n+1).n! $\geq (n+1).{(2^n)}^2 = (n+1).2^{2n}

since, n $\geq$ 9, so (n+1) > 4

Hence (n+1)! $\geq (n+1).2^{2n} > 4.2^{2n} = 2^{2(n+1)} = {(2^{n+1})}^2

(c) Base case: n = 0, 0! = 1 $\leq 2^{0^2}$

Induction step: Let n be an arbitrary natural number and n! $\leq 2^{(n^2)}$

Now, (n+1)! = (n+1).n! $\leq (n+1).2^{(n^2)} \leq (2^{(1+2n)}).2^{(n^2)} = 2^{(n+1)^2}$


Ex-13:
(a) Base case: n = 0, $(k^2)! \geq 1 = k^{2.0}$

Induction step: Let n be an arbitrary natural number s.t. $(k^2 + n)! \geq k^{2n}$

Now, $(k^2 + (n+1))! = (k^2 + n + 1).(k^2 + n)! \geq (k^2 + n + 1).k^{2n} = k^{2(n+1)} + (n+1).k^{2n} \geq k^{2(n+1)}$

(b) Base case: n = $2k^2$

by putting n = $k^2$ in part(a) result, we get

$(k^2 + k^2)! \geq k^{2k^2}$
=> $(2k^2)! \geq k^{2k^2}$

Induction step: Let n be an arbitrary natural number s.t $n \geq 2k^2$ and $n! \geq k^n$

Now, (n+1)! = (n+1).n! $\geq (n+1).k^n \geq k.k^n = k^{(n+1)}$


Ex-14: Let a be an arbitrary real number and m be an arbitrary natural number.

Base case: n = 0, ${(a^m)}^0 = 1 = a^{m(0)}$

Induction step: Let n be an arbitrary natural number and ${(a^m)^n = a^{mn}$

Now, ${(a^m)}^{(n+1)} = {(a^m)}^n.a^m = a^{(mn + m)} = a^{m(n+1)}$


Ex-15: Base case: n = 0, $a_0 = 0 = 2^0 - 0 - 1$

Induction step: Let $a_n = 2^n - n - 1$

Now, $a_{n+1} = 2a_n + n = 2(2^n - n - 1) + n = 2^{n+1} - 2n - 2 + n = 2^{n+1} - (n+1) - 1$


Ex-16: Scratchwork:
$a_n = {(a_{n-1})}^2 = {(a_{n-2})}^{2^2} = {(a_{n-3})}^{2^3} ... = {(a_{n-n})}^{2^n} = {a_0}^{2^n} = 2^{2^n}$

Thus $a_n = 2^{2^n}$

Proof:

Base case: n = 0, $a_0 = 2 = 2^1 = 2^{2^0}$

Induction step: Let $a_n = 2^{2^n}$

Now, $a_{n+1} = {(a_n)}^2 = {(2^{2^n})}^2 = 2^{2.2^n} = 2^{2^{(n+1)}}$


Ex-17: Scratchwork:
$a_1 = 1$
$a_2 = \frac{1}{2}$
$a_3 = \frac{1}{3}$
$a_4 = \frac{1}{4}$

..easy guess, $a_n = \frac{1}{n}$

Proof:

Base case: $a_1 = \frac{1}{1} = 1$

Induction step: Let $a_n = \frac{1}{n}$

Now, $a_{n+1} = \frac{a_n}{a_n + 1} = \frac{1/n}{(1/n) + 1} = \frac{1}{n+1}$

Note: In all the following exercises, [nCk] represents n-combination-k

Ex-18:
(a) [nC0] = $\frac{n!}{0!(n-0)!} = \frac{n!}{0!.n!} = \frac{n!}{n!.0!} = \frac{n!}{n!.(n-n)!}$ = [nCn]

(b) RHS
= [nCk] + [nC(k-1)]
= $\frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{n!.(n-k+1)}{k!(n-k+1)!} + \frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1).n!}{k!(n-k+1)!} - \frac{k.n!}{k!(n-k+1)!} + \frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1).n!}{k!(n-k+1)!} - \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1)!}{k!(n-k+1)!}$
= [(n+1)Ck]

(c) Base case: n = k, # of elements in $P_k(A)$ of a set A having k elements = 1 = [kCk]

Induction step: Let k be an arbitrary natural number. Let n be an arbitrary natural number s.t. $n \geq k$. For any set A, that has n elements, $P_k(A)$ has [nCk] elements.

Let A be a set containing n+1 elements and $a$ be an arbitrary element of A. Let us define a set B = A\{a}.

$P_k(A) = P_k(B) \cup \{ X \cup \{x\} | X \in P_{k-1}(B) \}$

Since $P_k$ and $\{ X \cup \{x\} | X \in P_{k-1}(B) \}$ are disjoint, so the # of elements in $P_k(A)$ = # of elements in $P_k(B)$ + # of elements in $\{ X \cup \{x\} | X \in P_{k-1}(B) \}$

Then, # of elements in $P_k(A)$ = [nCk] + [nC(k-1)] = [(n+1)Ck]

(d) Let x and y be arbitrary real numbers.

Base case: n = 0, LHS = $(x+y)^0 = 1 = [0C0]x^{0-0}y^0$

Induction step: Let $(x+y)^n$ = $\sum_{k=0}^{n} [nCk]x^{n-k}y^k$

Now, $(x+y)^{n+1}$

= $(x+y).(x+y)^n$
= $(x+y).\sum_{k=0}^{n} [nCk]x^{n-k}y^k$

= $(x+y)([nC0]x^n + [nC1]x^{n-1}y + [nC2]x^{n-2}y^2 + ... + [nCn]y^n)$

= $([nC0]x^{n+1} + [nC0]x^ny) + ([nC1]x^ny + [nC1]x^{n-1}y^2) + ([nC2]x^{n-1}y^2 + [nC2]x^{n-2}y^3) + ... + ([nCn]xy^n + [nCn]y^{n+1})$

= $x^{n+1} + ([nC0]x^ny + [nC1]x^ny) + ([nC1]x^{n-1}y^2 + [nC2]x^{n-1}y^2) + ... + ([nC(n-1)]xy^n + nCn]xy^n) + y^{n+1}$

= $x^{n+1} + [(n+1)C1]x^ny + [(n+1)C2]x^{n-1}y^2 + ... + [(n+1)Cn]xy^n + y^{n+1}$

= $[(n+1)C0]x^{n+1} + [(n+1)C1]x^ny + [(n+1)C2]x^{n-1}y^2 + ... + [(n+1)Cn]xy^n + [(n+1)C(n+1)]y^{n+1}$

= $\sum_{k=0}^{n+1} [(n+1)Ck]x^{n-k}y^k$


Ex-19:
(a) In Ex-18(d) put x = y = 1 to get

$(1+1)^n = \sum_{k = 0}^{n} [nCk]1^{n-k}1^k$
=> $2^n = \sum_{k=0}^{n}$

(b) Base case: For n = 1

LHS = $\sum_{k=0}^{1}{(-1)}^k[nCk] = {(-1)}^0[nC0] + {(-1)^1}[nC1] = 1 - 1 = 0$ = RHS

Induction step: Let $\sum_{k=0}^{n}{(-1)}^k[nCk] = 0$

Now, $\sum_{k=0}^{n+1}{(-1)}^k[(n+1)Ck]$

= ${(-1)}^0[(n+1)C0] + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}[(n+1)C(n+1)]$

= ${(-1)}^0 + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k([nCk] + [nC(k-1)]) + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k[nCk] + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $({(-1)}^0[nC0] + \sum_{k=1}^{n}{(-1)}^k[nCk]) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $(\sum_{k=0}^{n}{(-1)}^k[nCk]) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $(0) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $\sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

Let, l = k-1, then k = l+1. Now above expression becomes

= $\sum_{l=0}^{n-1}{(-1)}^{l+1}[nCl] + {(-1)}^{n+1}$

= $\sum_{l=0}^{n-1}{(-1)}^{l+1}[nCl] + {(-1)}^{n+1}[nCn]$

= $\sum_{l=0}^{n}{(-1)}^{l+1}[nCl]$

= $-\sum_{l=0}^{n}{(-1)}^l[nCl]$

= 0


Ex-20: As given in the hint, we will prove that for all $n \geq 1$, $0 < a_n < \frac{1}{2}$

Base case: For n = 1
$a_1 = {(a_0)}^2 + \frac{1}{4} = \frac{1}{4}$

clearly, $0 < a_1 < \frac{1}{2}$

Induction step: Let n be arbitrary natural number greater than or equal to 1 and $0 < a_n < \frac{1}{2}$

Now, $a_{n+1}$
= ${(a_n)}^2 + \frac{1}{4}$
> 0

Also, $a_{n+1}$
= ${(a_n)}^2 + \frac{1}{4}$
< ${(\frac{1}{2})}^2 + \frac{1}{4}$
= $\frac{1}{4} + \frac{1}{4}$
= $\frac{1}{2}$

Thus, $0 < a_{n+1} < \frac{1}{4}$