induction

e.g. Prove $\displaystyle\sum_{k=1}^n f(k)=F(n)$ is true for all $n>0$ .
We have to prove that
1. $f(1)=F(1)$
2. $F(n)+f(n+1)=F(n+1)$ i.e. if formula works for $F(n)$ , it also works for $F(n+1)$ .

Prove that for $n>0, \quad\displaystyle 1\cdot2+2\cdot3+\cdots+n(n+1)=\frac{n(n+1)(n+2)}{3}$
Solution. $f(1)=1\cdot2=\frac{1\cdot2\cdot3}{3}=F(1)$

$\begin{align*} F(n+1)-F(n)&=\frac{(n+1)(n+2)(n+3)}{3}-\frac{n(n+1)(n+2)}{3} \\ &=(n+1)(n+2) \\ &=f(n+1) \end{align*}$

■