Loading [MathJax]/jax/output/HTML-CSS/jax.js




MATH 300 Fall 2018 Problems from Chapter 10

Mathematical Induction

The following is the list of problems for Chapter 10 of the Book of Proof (page 169). There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

Prove the following statements with either induction, strong induction or proof by smaller counterexample.

  1. For every integer nN, it follows that 1+2+3+4++n=n2+n2.
  2. For every integer nN, it follows that 12+22+32+42++n2=n(n+1)(2n+1)6.
  3. For every integer nN, it follows that 13+23+33+43++n3=n2(n+1)24.
  4. If nN, then 12+23+34+45++n(n+1)=n(n+1)(n+2)3.
  5. If nN, then 21+22+23++2n=2n+12.
  6. For every natural number n, it follows that nk=1(8k5)=4n2n.
  7. If nN, then 13+24+35+46++n(n+2)=n(n+1)(2n+7)6.
  8. If nN, then 12!+23!+34!++n(n+1)!=11(n+1)!.
  9. For any integer n0, it follows that 24|(52n1).
  10. For any integer n0, it follows that 3|(52n1).
  11. For any integer n0, it follows that 3|(n3+5n+6).
  12. For any integer n0, it follows that 9|(43n+8).
  13. For any integer n0. it follows that 6|(n3n).
  14. Suppose that aZ. Prove that 5|2na implies 5|a for any nN.
  15. If nN, then 112+123+134+145+dotsb+1n(n+1)=11n+1.
  16. For every natural number n, it follows that 2n+13n.
  17. Suppose A1,A2,,An are sets in some universal set U, and n2. Prove that (A1A2An)=A1A2An.
  18. Suppose A1,A2,,An are sets in some universal set U, and n2. Prove that (A1A2An)=A1A2An.
  19. Prove that 11+14+19++1n221n.
  20. Prove that (1+2+3++n)2=13+23+33++n3 for every nN.
  21. If nN, then 11+12+13+14+15++12n1+12n1+n2.
  22. If nN, then (112)(114)(118)(1116)(112n)14+12n+1.
  23. Use mathematical induction to prove the binomial theorem (use equation (3.2) on page 78.)
  24. Prove that nk=1k(nk)=n2n=1 for each natural number n.
  25. Concerning the Fibonacci sequence, prove that F1+F2+F3+F4++Fn=Fn+21.
  26. Concerning the Fibonacci sequence, prove that nk=1F2k=FnFn+1.
  27. Concerning the Fibonacci sequence, prove that F1+F3+F5+F7++F2n1=F2n.
  28. Concerning the Fibonacci sequence, prove that F2+F4+F6+F8++F2n=F2n+11.
  29. In this problem nN and Fn is the nth Fibonacci number. Prove that (n0)+(n11)+(n22)+(n33)++(0n)=Fn+1.
  30. Here Fn is the nth Fibonacci number. Prove that Fn=ϕn1ϕn25, where ϕ1=1+52 and ϕ2=152.
  31. Prove that nk=0(kr)=(n+1r+1), where 1rn.
  32. Prove that the number of n-digit binary numbers that have no consecutive 1’s is the Fibonacci number Fn+2.
  33. Suppose n straight lines lie on a plane in such a way that no two of the lines are parallel, and no three of the lines intersect at a single point. Show that this arrangement divides the plane into n2+n+22 regions.
  34. Prove that 31+32+33+34++3n=3n+132 for every nN.
  35. Prove that if n,kN, and n is even and k is odd, then (nk) is even.
  36. Prove that if n=2k1 for some kN, then every entry in the nth row of Pascal’s triangle is odd.
  37. Prove that if m,nN, then nk=0k(m+km)=n(m+n+1m+1)(m+n+1m+2).
  38. Prove that if n is a positive integer, then (n0)2+(n1)2+(n2)2++(nn)2=(2nn).
  39. Prove that if n is a positive integer, then (n+00)+(n+11)+(n+22)++(n+kn)=(n+k+1k).
  40. Prove that pk=0(mk)(npk)=(m+np) for positive integers m,n and p..
  41. Prove that mk=0(mk)(np+k)=(m+nm+p) for positive integers m,n and p..