# induction with remainders

$$a_n= \sum_{i=0}^5 (n+i)^2$$

I have to prove by induction that for every natural $n$ (including $0$ in this case) that if you divide $a_n$ by $12$ you will always get a remainder of $7$. so i proved the base case which was n=0

Then I started my induction step which was to take $a_n+1 - a_n$ (i got help there because i don't understand why to subtract for my induction step)

It all equals $(n+6)^2-n^2 = 12n+36 = 12(n+3)$

so my problem is that i have to show that this will give me a remainder of $7$ when divided $12$ but it won't because its all a multiple of $12$. So where did i go wrong??

• i have to show that this will give me a remainder of 7 when divided 12 No, if both $a_n$ and $a_{n+1}$ are $\equiv 7 \pmod{12}$ then the difference $a_{n+1}-a_n$ will give remainder $\dots$ – dxiv Dec 9 '16 at 20:26

You have proved that $a_0=7|12$

Now assume that $a_n=7|12$

Now Once you have proved that $a_{n+1}-a_n=0|12$ you get $$a_{n+1}=a_n|12=7|12$$

There you induction step goes.

Now do you understand why we did $a_{\color{red}{n+1}}-a_{\color{red}{n}} ?$

It all equals $$\sum_{i=0}^5 (n+i)^2=6n(n+5)+55\equiv 7\bmod 12,$$ because $n(n+5)\equiv 0\bmod 2$. If you have to prove it by induction, then you assume $a_n\equiv 7\bmod 12$, and then show that $$a_{n+1}\equiv a_n\equiv 7\bmod 12.$$

The key idea is that a sequence $\,a_n\,$ is constant $\,a_n\equiv a_0\equiv 7\,$ if it $\color{#c00}{\text{never changes value.}}$

Lemma $\$ The sequence $\,a_n\,$ satisfies $\,a_n \equiv a_0\,$ for all $\,n\ge 0\,$ if $\,\color{#c00}{a_{n+1} \equiv a_{n}}\,$ for $\,n\ge 0$

Proof $\$ The base case is clear, and $\,a_n\equiv a_0\, \Rightarrow\, \color{#c00}{a_{n+1}\equiv a_n}\equiv a_0\,$ is the induction step.

You have proved that $\ 7\mid a_{n+1}-a_n,\$ i.e.  that $\ \color{#c00}{a_{n+1}\equiv a_n}\pmod{7},\,$ so the Lemma applies.

Remark $\$ The proof is a special case of telescopy since we can write $\,a(n) = a_n\,$ as a telescoping sum of its successive differences $\displaystyle \, a(n)\, =\, a(0) + {\sum_{k=0}^{n-1}\, \overbrace{a(n\!+\!1)-a(n)}^{\large\color{#c00}0}}\$ i.e.

$$\color{#c00}{a(0)}\, =\, \underbrace{\color{#c00}{a(0)}\phantom{-a(0)}}_{\Large\color{#0a0}0}\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{-\,a(0) +\!\phantom{a(1)}}^{\Large\!\!\!\!\! \ \ \ \, \color{#c00}{0}} \!\!\!\!\!\!\!\!\!\! \underbrace{a(1) -a(1)}_{\Large\color{#0a0}0}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\phantom{-a(1)}\!+ a(2)}^{\Large \!\!\!\!\!\!\!\!\!\!\! \quad\ \ \ \color{#c00}{0} }\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{a(2)}-a(2)}_{\Large\color{#0a0}0}\!+\: \overbrace{\underbrace{\cdots\phantom{I_{I_I}\!\!\!\!\!\!\!\!}}_{\Large\color{#0a0}0}+\,\color{#0a0}{a(n)}}^{\Large \!\!\!\!\! \ \ \ \color{#c00}{0}}\ =\ \color{#0a0}{a(n)}$$

The induction essentially rebrackets the sum from the green bracketing $\,\color{#0a0}{0+\cdots0 +a(n)}\,$ into the red bracketing $\,\color{#c00}{a(0)+0+\cdots0},\,$ using the associativity of addition. For further details on this ubiquitous telescopic form of induction, see this answer and its links.

• Thats colourful ! – Qwerty Dec 10 '16 at 10:45