Wednesday, June 30, 2010

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 = 1a_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}\$

1. Hello, in exercise 10, in this step:

= ∑(i(i!)) + (n+1).(n+1)!
= (n+1)! - 1 + (n+1).(n+1)!

wouldn't ∑(i(i!)) then be n!-1 as stated in the supposition?
Can you explain this step?

Thank you!

1. @cmkwadedrums: Thanks, there was a mistake in the hypothesis. I corrected it. I hope it is self-explanatory now.

2. This comment has been removed by the author.