Saturday, June 26, 2010

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 nNP(n):
First prove P(0), and then prove nN(P(n)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 nN(P(n)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 nN(P(n)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 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 = n(n+1)2

Now, 0 + 1 + 2 + ... + n + (n+1)
= n(n+1)2 + (n+1)
= (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. 02+12+22+...+n2=(n(n+1)(2n+1)6

Now, 02+12+22+...+n2+(n+1)2
= (n(n+1)(2n+1)6+(n+1)2
= (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. 03+13+23+...+n3=[(n(n+1)2]2

Now, 03+13+23+...+n3+(n+1)3
= [(n(n+1)2]2+(n+1)3
= (n+1)2(n2+4(n+1))4
= [(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) = n2. Let us try to prove it now.

Formal Proof:

Base case: For n = 1, LHS = 1 and RHS = 12 = 1. cleary LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. n1 and 1 + 3 + 5 ... + (2n-1) = n2

Now, 1 + 3 + 5 + ... + (2n-1) + (2n+1)
= n2+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) = n(n+1)(n+2)3

Now, 0.1 + 1.2 + 2.3 + ... + n(n+1) + (n+1)(n+2)
= n(n+1)(n+2)3 + (n+1)(n+2)
= (n+1)(n+2)(n+3)3


Ex-6: Scratchwork: My guess using results of ex1,5 is 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) = 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)
= n(n+1)(n+2)(n+3)4 + (n+1)(n+2)(n+3)
= (n+1)(n+2)(n+3)(n+4)4


Ex-7: Guess is 3n+1-12

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

Induction step:
Let n be arbitrary natural number s.t. 30+31+32+...+3n=3n+1-12

30+31+32+...+3n+3n+1
= 3n+1-12+3n+1
= 3n+2-12


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-12+13-14+...+12n-1-12n=1n+1+1n+2+...+12n

Now, 1-12+13-14+...+12n-1-12n+12n+1-12n+2
= 1n+1+1n+2+...+12n+12n+1-12n+2
= 1n+2+...+12n+12n+1-12n+2+1n+1
= 1n+2+...+12n+12n+1+12n+2


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

(n+1)2+(n+1)
= n2+2n+1+n+1
= (n2+n)+2(n+1)
= 2(k + n + 1)

clearly, 2[(n+1)2+(n+1)]

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

Now, (n+1)3-(n+1)
= n3+1+3n2+3n-n-1
= (n3-n)+3(n2+n)

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

So, (n+1)3-(n+1)
= (n3-n)+3(n2+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 90-8(0)-1=0
Induction step:
Let n be arbitrary natural number s.t. 64 divides 9n-8n-1. Then we can choose some integer k s.t. 9n-8n-1=64k

Now, 9n+1-8(n+1)-1
= 9.9n-8n-9
= 9(9n-8n-1)+64n
= 9(64k) + 64n
= 64(9k + 1)

clearly 64 divides 9n+1-8(n+1)-1


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

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

clearly 9 divides 4n+1+6(n+1)-1


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

Now, an+1-bn+1
= a(an-bn)+abn-bn+1
= a(an-bn)+bn(a-b)
= (a-b)(ka+bn)


clearly (a-b) divides an+1-bn+1


Ex-13: Base case: For n = 0, clearly (a+b) divides a2(0)+1+b2(0)+1=(a+b)
Induction step:
Let n be arbitrary natural number s.t. (a+b) divides a2n+1+b2n+1

Now, a2(n+1)+1+b2(n+1)+1
= a2n+3+b2n+3
= a2(a2n+1+b2n+1)-a2b2n+1+b2n+3
= a2(a+b)k-b2n+1(a2-b2)
= (a+b)(a2k-b2n+1(a-b))

clearly (a+b) divides a2(n+1)+1+b2(n+1)+1


Ex-14: Base case: For n = 10, 210=1024>103=1000
Induction step:
Let n be arbitrary natural number s.t. 2n>10n

Now, 2n+1
= 2.2n
> 2n3 = n3+n3 = n3+10n2 (bacause n10)
= n3+3n2+3n2+n2
> n3+3n2+3n+1 = (n+1)3

clearly 2n+1>(n+1)3


Ex-15: Base case: For n = 0, clearly 00(mod3)
Inductive step:
Let n be a arbitrary natural number s.t. n0(mod3) or n1(mod3) or n2(mod3). Let us consider all the possible cases for (n+1)

Case#1: n0(mod3)
Then we can choose some integer k s.t. n = 3k. Then (n + 1) = 3k + 1. Then (n+1)-1=3k. Thus (n+1)1(mod3)

Case#2: n1(mod3)
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)2(mod3)

Case#3: n2(mod3)
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)0(mod3)

Thus (n+1)0(mod3) or (n+1)1(mod3) or (n+1)2(mod3)


Ex-16: Base case: For n = 1. LHS = 2.21 = 4, RHS = (1)21+1=4. clearly LHS = RHS
Induction Step:
Let n be arbitrary natural number s.t. 2.21+3.22+4.23+...+(n+1)2n=n2n+1

Now, 2.21+3.22+4.23+...+(n+1)2n+(n+2)2n+1
= n2n+1+(n+2)2n+1
= n2n+1+n2n+1+2n+2
= n2n+2+2n+2
= (n+1)2n+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.30+3.31+5.32+...+(2n+1)3n
3P(n) = 1.31+3.32+...+(2n-1)3n+(2n+1)3n+1

P(n) - 3P(n) = 1.30+2.31+2.32+....+2.3n-(2n+1)3n+1
P(n) - 3P(n) = -1.30+2(30+31+32+...+3n)-(2n+1)3n+1 ,now use result of ex-7
P(n) - 3P(n) = -1+23n+1-12-(2n+1)3n+1
2P(n) = 1-23n+1-12+(2n+1)3n+1
2P(n) = 1-3n+1+1+(2n+1)3n+1
2P(n) = 2+2n3n+1
P(n) = 1+n3n+1

So, 1.30+3.31+5.32+...+(2n+1)3n=1+n3n+1

Formal Proof:

Base case: For n = 0. LHS = 1.30 = 1, RHS = 1+(0)30+1 = 1 + 0 = 1

Induction step:
Let n be arbitrary natural number s.t. 1.30+3.31+5.32+...+(2n+1)3n=1+n3n+1

Now, 1.30+3.31+5.32+...+(2n+1)3n+(2n+3)3n+1
= 1+n3n+1+(2n+3)3n+1
= 1+n3n+1+2n3n+1+3.3n+1
= 1+3n3n+1+3n+2
= 1+(n+1)3n+2


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

Induction step:

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

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

Case#2: n is odd and an<0
(n+1) is even. And an+1 = a.an. Since a is negative and also an is negative, so an+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<an<bn.

clearly, 0<an+1.

Now, bn+1=bbn>ban>aan=an+1
Thus, 0<an+1<bn+1

(b) TODO

(c) We'll prove the inequality directly.
inequality to prove is, abn+ban<an+1+bn+1. it can rewritten as an+1+bn+1-abn-ban>0

Now an+1+bn+1-abn-ban
= an+1-abn+bn+1-ban
= a(an-bn)-b(an-bn)
= (a-b)(an-bn)
= (b-a)(bn-an)

from part(a), an<bn
=> (bn-an)>0

also (b-a) > 0

Hence an+1+bn+1-abn-ban = (b-a)(bn-an) > 0

(d) Base case: For n = 2,
(a+b2)2=a2+b24+2ab4

In part(c), putting n = 1 gives
ab+ba<a2+b2
=> 2ab<a2+b2

So, (a+b2)2
= a2+b24+2ab4
< a2+b24+a2+b24 = a2+b22

Induction step:
Let n be arbitrary natural number greater than or equal to 2 s.t. (a+b2)n<an+bn2

Multiplying both sides of above inequality with a+b2, we get

(a+b2)n+1<an+bn2.a+b2
=> (a+b2)n+1<an+1+bn+1+ban+abn4

from part(c), abn+ban<an+1+bn+1
so, an+1+bn+1+ban+abn4<2(an+1+bn+1)4=an+1+bn+12

Hence, (a+b2)n+1<an+1+bn+12

No comments:

Post a Comment