We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).