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.
- For every integer n∈N, it follows that 1+2+3+4+⋯+n=n2+n2.
- For every integer n∈N, it follows that 12+22+32+42+⋯+n2=n(n+1)(2n+1)6.
- For every integer n∈N, it follows that 13+23+33+43+⋯+n3=n2(n+1)24.
- If n∈N, then 1⋅2+2⋅3+3⋅4+4⋅5+⋯+n(n+1)=n(n+1)(n+2)3.
- If n∈N, then 21+22+23+⋯+2n=2n+1−2.
- For every natural number n, it follows that ∑nk=1(8k−5)=4n2−n.
- If n∈N, then 1⋅3+2⋅4+3⋅5+4⋅6+⋯+n(n+2)=n(n+1)(2n+7)6.
- If n∈N, then 12!+23!+34!+⋯+n(n+1)!=1−1(n+1)!.
- For any integer n≥0, it follows that 24|(52n−1).
- For any integer n≥0, it follows that 3|(52n−1).
- For any integer n≥0, it follows that 3|(n3+5n+6).
- For any integer n≥0, it follows that 9|(43n+8).
- For any integer n≥0. it follows that 6|(n3−n).
- Suppose that a∈Z. Prove that 5|2na implies 5|a for any n∈N.
- If n∈N, then 11⋅2+12⋅3+13⋅4+14⋅5+dotsb+1n(n+1)=1−1n+1.
- For every natural number n, it follows that 2n+1≤3n.
- Suppose A1,A2,…,An are sets in some universal set U, and n≥2. Prove that (A1∩A2∩⋯∩An)∁=A∁1∪A∁2∪⋯∪A∁n.
- Suppose A1,A2,…,An are sets in some universal set U, and n≥2. Prove that (A1∪A2∪⋯∪An)∁=A∁1∩A∁2∩⋯∩A∁n.
- Prove that 11+14+19+⋯+1n2≤2−1n.
- Prove that (1+2+3+⋯+n)2=13+23+33+⋯+n3 for every n∈N.
- If n∈N, then 11+12+13+14+15+⋯+12n−1+12n≥1+n2.
- If n∈N, then (1−12)(1−14)(1−18)(1−116)⋯(1−12n)≥14+12n+1.
- Use mathematical induction to prove the binomial theorem (use equation (3.2) on page 78.)
- Prove that ∑nk=1k(nk)=n2n=1 for each natural number n.
- Concerning the Fibonacci sequence, prove that F1+F2+F3+F4+⋯+Fn=Fn+2−1.
- Concerning the Fibonacci sequence, prove that ∑nk=1F2k=FnFn+1.
- Concerning the Fibonacci sequence, prove that F1+F3+F5+F7+⋯+F2n−1=F2n.
- Concerning the Fibonacci sequence, prove that F2+F4+F6+F8+⋯+F2n=F2n+1−1.
- In this problem n∈N and Fn is the nth Fibonacci number. Prove that (n0)+(n−11)+(n−22)+(n−33)+⋯+(0n)=Fn+1.
- Here Fn is the nth Fibonacci number. Prove that Fn=ϕn1−ϕn2√5, where ϕ1=1+√52 and ϕ2=1−√52.
- Prove that ∑nk=0(kr)=(n+1r+1), where 1≤r≤n.
- Prove that the number of n-digit binary numbers that have no consecutive 1’s is the Fibonacci number Fn+2.
- 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.
- Prove that 31+32+33+34+⋯+3n=3n+1−32 for every n∈N.
- Prove that if n,k∈N, and n is even and k is odd, then (nk) is even.
- Prove that if n=2k−1 for some k∈N, then every entry in the nth row of Pascal’s triangle is odd.
- Prove that if m,n∈N, then ∑nk=0k(m+km)=n(m+n+1m+1)−(m+n+1m+2).
- Prove that if n is a positive integer, then (n0)2+(n1)2+(n2)2+⋯+(nn)2=(2nn).
- Prove that if n is a positive integer, then (n+00)+(n+11)+(n+22)+⋯+(n+kn)=(n+k+1k).
- Prove that ∑pk=0(mk)(np−k)=(m+np) for positive integers m,n and p..
- Prove that ∑mk=0(mk)(np+k)=(m+nm+p) for positive integers m,n and p..