Homework 8

1. Consider the sequence $(B_n)$ defined recursively by,

   • $B_0 = 0$
   • for $n:\mathbb{N}$, $B_{n+1} = B_n+(n+1)^2$.

   Thus $B_n$ represents the sum $1^2+2^2+3^2+\cdots+n^2$. Show that for all natural numbers $n$, $B_n = \frac{n(n+1)(2n+1)}{6}$.

2. Consider the sequence $S_n$ defined recursively by,

   • $S_0=1$
   • for $n:\mathbb{N}$, $S_{n+1} = S_n+\frac{1}{2^{n+1}}$.

   Thus $S_n$ represents the sum $1+\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2^n}$. Show that for all natural numbers $n$, $S_n=2-\frac{1}{2^n}$.

3. Consider the sequence $a_n$ defined recursively by,

   • $a_0=4$
   • for $n:\mathbb{N}$, $a_{n+1} = 3a_n-5$.

   Show that for all sufficiently large natural numbers $n$, $a_n\geq 10 \cdot 2^n$.

4. Consider the sequence $c_n$ defined recursively by,

   • $c_0=3$
   • $c_1=2$
   • for $n:\mathbb{N}$, $c_{n+2}=4c_n$.

   Prove that for all natural numbers $n$, $c_n=2\cdot 2^n+(-2)^n$.

5. Consider the sequence $q_n$ defined recursively by,

   • $q_0=1$
   • $q_1=2$
   • for $n:\mathbb{N}$, $q_{n+2}=2q_{n+1}-q_n+6n + 6$.

   Prove that for all natural numbers $n$, $q_n=n^3+1$.

6. Show that for all natural numbers $n>0$, there exist natural numbers $a$ and $x$, with $x$ odd, such that $n=2^ax$.

   Suggested approach: start with a case split on the parity of $n$, using the lemma Nat.even_or_odd.

   Note: this problem should be solved by strong induction -- in class on Thursday we covered strong induction for proofs in words but not for proofs in Lean. So start by solving this problem in words only -- in class on Monday you will learn how to translate your proof into Lean.