Proof by induction for recursions

Question

I want to proof that: $$a_i = i^2 + a_{i-1} = {i(i+1)(2i+1) \over 6}$$ $$i \in \mathbb{N_0}; a_0 = 0$$ by induction. However I get stuck on the recursiveness of $a_{i-1}$. Ideas how to build the proof without it / how to work it in ?

Answer 1

Suppose $a_i=i^2+a_{i-1}=\frac{i(i+1)(2i+1)}{6}$ for some $i\in\mathbb{N}_0$. We wish to prove that $a_{i+1}=(i+1)^2+a_i=\frac{(i+1)(i+2)(2(i+1)+1)}{6}$.

Now, we have $a_{i+1}=i^2+2i+1+a_i$ by definition of the sequence, and thus $$a_{i+1}=i^2+2i+1+\frac{i(i+1)(2i+1)}{6}$$ by inductive hypothesis. Finally, expand and simplify this expression and you will get what you wanted, which was$$a_{i+1}=\frac{(i+1)(i+2)(2i+3)}{6}$$

Answer 2

Proofs by induction work so that you assume the formula holds for $a_{i-1}$ -- you don't need to prove it. Assuming that, then what you need to show is that it holds for $a_i$.

Answer 3

Base case

if $i=0$ it works. as $${0\over 6}=0$$ Induction

if $i=k$ works, the $i=k+1$ leads to :$${(2k^3+3k^2+k)+(k^2+2k+1)\over 6}={2k^3+9k^2+13k+1\over 6}$$

where the denominator factors as $$(k+1)(k+2)(2k+3)=i(i+1)(2i+1)$$ really the hard part here, is remembering that $i^2$ adds the denominator times itself to the numerator and refactoring the numerator in terms of the new $i$ value.