Exercises
63
13. Find the smallest n E N such that 2n
2 + 3n + 1 < n
3 .
14. Prove by induction for n > 0:
2+4+6+...+2n
=n
2 +n
15. Prove by induction:
(a) 1
2 +2
2 +3
2 +...+n
2 =n(n+1)(2n+1)/6forn >0
(b) 1
3 +2
3 +3
3 +..+n
3 = (+2+3+...--+n)
2 forn >0
(c) 1
4 +2
4 +3
4 +... + n4 = n (n + 1) (2n + 1) (3n2 + 3n - 1)/30 for n > 0
(d) 1
5 +2
5 +3
5 +...+n
5 =ln
6 +an6 +n
4
- nzforn_>0
122 n_
nfo
16. Prove by induction:
(a) 0.2
0
°1.2
1 +2.2
2 +3.2
3 +...+n.2n =(n-1)2n+1+2forn >0
(b) 12 +32 +52 + .. ±
+ (2n + 1)2 - (n + 1) (2n + 1) (2n + 3)/3 for n > 0
(c) 1
2 -2
2 +32 + ... + (-1)n-1 n
2 = (-1)n-' n (n + 1)/2 for n > 0
(d) 1.2±2.3+ 3.4+...+n.(n+ 1)=n(n+
1)(n+2)/3forn >0
(e) 1.2.3+2.3.4+ 3.4.5+...+n.(n+
1).(n+2)=n(n+ 1)(n+2)
(n + 3)/4 for n > 0
17. Prove by induction:
1
1
1
(a) + _ +
+ n (n-l)
fornnl>-(b) 1
2 23
..
= 2
f2
18. Prove by induction that 8 divides (2n + 1)2 - 1 for all n E N.
19. Prove by induction for n > 0:
(a) 3 divides n
3 + 2n
(b) 5 divides n
5 - n
(c) 6 divides n
3 - n
(d) 6 divides n
3 + 5n
20. Prove by induction for all n E N:
(a) 7 divides n
7 - n
(b) 11 divides n
11 - n
(c) 13 divides n
13 - n
(d) 120 divides n
5 - 5n
3 + 4n
21. Prove by induction: The sum of the cubes of any three consecutive natural numbers is
divisible by 9.
22. Show that any integer consisting of 3n identical digits is divisible by 3n. Verify this for
222; 777; 222,222,222; and 555,555,555. Prove the general statement for all n e N by
induction.
23. Prove by induction that the following identities are true for the Fibonacci numbers:
(a) y
0 F 2i +1 = F2n+2 - 1 for n > 0
(b) y•n I Fi2 = Fn"- Fn,+l I for n _> I
(c)
Fi=0 Fn+z-lforn>0
24. Find the Fibonacci numbers F 8 through F 15 . Prove the following results for the Fibonacci numbers:
(a) F3n and F3n+l are odd, and F3n+2 is even for n > 0
(b) Fo + F 2 + ... + F 2 n = F 2 n+l for n > 0