Introductory Discrete Mathematics 2

Introductory Discrete Mathematics
Page 156
Question 4
b. n3+(n+1)3+(n+2)3Is divisible by 9 for all n≥1Proof
The base case in this situation is n=0 which implies that
n3+(n+1)3+(n+2)3=03+13+23=9 This is divisible by 9. Therefore, the basis holds true for n=0The inductive hypothesis becomes n=k≥0, k3+k+13+(k+2)3 is also divisible by 9
→ k3+k+13+(k+2)3=9p…(i)By inductionn=k+1, equation (i) becomes
(k+1)3+(k+2)2+(k+3)3=9p-k3+k+33…(ii)
Simplifying (ii) we have
=9p-k3+k+33=9p-k3+k3+9k2+9k+27=9p+9k2+k+3=9(p+k2+k+3)This implies that (k+1)3+(k+2)2+(k+3)3 is also divisible by 9 therefore, n3+(n+1)3+(n+2)3is divisible by 9 for all n≥1
d. 83 – 3n Is divisible by 5 for all n≥1Proof
If n=1 then, 8n-3n= 81+31=5 this can be divided by 5. Therefore, the basis holds true for n=1The inductive hypothesis becomes n=k ≥1. It means that 8k-3k is divisible by 5
→8k-3k=5p…(i)By induction, taking n=k+1 we have,
8k+1-3k+1=88k-33k=38k-3k+5×8k…(ii)But 8k-3k=5p for some integer p. therefore, ii becomes
=(3×5p)+(5×8k) Simplifying we get
=5(3p+8k) Which is divisible by 5 implying that 8n – 3n is divisible by 5 for all n≥1
g. n3+5n Is divisible by 6 for all n≥1
Proof
If n=1 then n3+5n=13+5×1=6, this is divisible by 6. Therefore, the basis holds true for n=1.
By induction, we can assume that for some k, k3+5k can be divided by 6
Therefore, (k+1)3+5(k+1) should be divisible by 6. It also means that k3+5k=6p given some integer p.
Expanding we have
k+13+5k+1=k3+3k2+3k+1+5k+5=k3+3k2+8k+6=6p+1+3k2+3k (Since k3+5k=6p)…(i)In case k is an even number, then k=2x for some integer x.

Substituting this value in equation (i) we have,
6p+1+3k2+3=6p+1+3(4×2)+3(2x)=6p+1+62×2+6x=6(p+2×2+x+1)
Which is divisible by 6. Therefore, n3+5n is divisible by 6 for all n≥1Question 5
b. 13+2+…+n3=n2(n+1)24 For any natural number n. Proof
Assuming that the equation is defined as Pn: 13+2+…+n3=n2(n+1)24 then when n=1 we have,
12(1+1)24=12224=1 Therefore, P1 is true.
If we assume that Pk is also true, then we have
13+23+…+k3=k2(k+1)2413+23+…+k3+ k+13=k2k+124+k+13Factoring out k+12 the LHS becomes =k+12(k24+k+1)=k+12(14k2+4k+4)=k+12(k+2)24=k+12[k+1+1]24It means that Pk holds true for Pk+1.
Since P1 true and Pk→P(k+1) is also true, then 13+2+…+n3=n2(n+1)24 for any natural number n.
Question 6
a. 1+2+22+23+…+2n= 2n+1-1 For all n≥1Proof
The simplified equation becomes 2+22+23+…+2n= 2n+1-2In this situation, the base case is n=1. Using this value, we have
2+22+23+…+2n= 21=2Also, 2n+1-2=21+1-2=4-2=2Therefore, the statement holds true for n=1Assuming that n=k holds, we have
2+22+23+…+2k= 2k+1-2Taking n=k+1,
2+22+23+…+2k+ 2k+1=[2+22+23+…+2k]+ 2k+1=2k+1-2+2k+1=21*2k+1-2=2k+1+1-2The hypothesis holds true for n=k+1. Therefore, 1+2+22+23+…+2n= 2n+1-1 for all n≥1e. 11*2+12*3+13*4+…+1nn+1=nn+1 For all n≥1Proof
Taking the base case to be n=1 and comparing the RHS with the LHS we have
11*2=11(1+1)Therefore the RHS = LHS and the proposition is true for n=1For n=k≥1, the equation becomes
11*2+12*3+13*4+…+1k*k+1=nk+1If n=k+1 then we have
11*2+12*3+13*4+…+1k*k+1+1k+1*k+2=kk+1+1k+1*k+2=k*k+2+1(k+1)*(k+2)=k2+2k+1(k+1)*(k+2)=(k+1)2(k+1)*(k+2)=(k+1)(k+2)=(k+1)(k+1+1)…(i)Since k+1=n, i becomes nn+1 proving that 11*2+12*3+13*4+…+1nn+1=nn+1 for all n≥1Question 8
b. i=1ni22i-1(2i+1)=n(n+1)22n+1When n=1 the RHS is =1(1+1)22*1+1=13 and the LHS is i22i-1(2i+1)=14+2i-2i-1=13The RHS=LHS, therefore, the equation is right for n=1Suppose that the equation holds for n=k, then we have
i=1k+1i22i-1(2i+1)=i=1ki22i-1(2i+1)+(k+1)2(2k+1-1)(2k+1+1))Through induction hypothesis we have
=k(k+1)2k-1(2k+1)+(k+1)22k+1-1(2(k+1)+1)=k(k+1)22k+1+(k+1)22k+1(2k+3)=k2k+3k+1+2(k+1)22(2k+1)(2k+3)Therefore, the equation holds for n=k+1Question 9
d. (1+12)n≥n2, for n ∈ N
Proof
When n=1, then (1+12)1≥12 →112≥12, therefore, the inequality holds true
Supposing that (1+12)k≥k2 is true for some positive integer k that is for n=k, then for the case of n=k+1, we have
(1+12)k+1=k+12Considering the LHS =(1+12)k(1+12)1≥(k+12)(1+12)1=32k+12=34(k+1)But k+1=n, therefore we have 34n. since (1+12)n≥34n, the inequality holds for both cases of n=k and n=k+1. It means that (1+12)n≥n2, for n ∈ N
g. 11*. 2 +12*3+ 13*4+…+1nn+1=nn+1
Proof
If n=1 then we have
11*2=11(1+1)Therefore the RHS = LHS and the proposition is true for n=1For n=k≥1, the equation becomes
11*2+12*3+13*4+…+1k*k+1=nk+1If n=k+1 then we have
11*2+12*3+13*4+…+1k*k+1+1k+1*k+2=kk+1+1k+1*k+2=k*k+2+1(k+1)*(k+2)=k2+2k+1(k+1)*(k+2)=(k+1)2(k+1)*(k+2)=(k+1)(k+2)By induction, the inequality holds true for both n=k and n=k+1
Workbook 78
42. 13+23+33+…+n3=n2(n+1)24Proof
When n=1 we have,
12(1+1)24=12224=1Therefore, n=1 is true
Since (1+2+3+…+n)2=[nn+12]2=n2(n+1)24 for n≥1Therefore, (1+2+3+…+n)2=13+23+33+…+n3=n2(n+1)24 for all n≥1
For a given integer k, n=k
13+23+33+…+k3=k2(k+1)24…(i)n=k+1 Should also be true. That is,
13+23+33+…+k3+k+13=k2(k+1)24+k+13=(k+1)2[k2 4+k+1]=(k+1)2(k+2)24=(k+1)2(k+1+1)24Thus n=k+1 is also true implying that 13+23+33+…+n3=n2(n+1)2444. 1+10+100+…+10n=10n+1-19Proof
In this situation, the base case is n=0→10(0+1)-19=10-19=99=1Therefore n=0 is true
If n=k, k being an integer we have,
1+10+100+…+10k=10k+1-19For the equation to hold, n=k+1 should also be true. The equation therefore translates to
1+10+100+…+10k+1=10k+1+1-19=10k+2-19=10k+1+1-19=10k+1*101-19Thus n=k and n=k+1 are true implying that 1+10+100+…+10n=10n+1-19