$$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??

  • $\begingroup$ 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$ $\endgroup$ – 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.

  • $\begingroup$ Thats colourful ! $\endgroup$ – Qwerty Dec 10 '16 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.