Inductive proof of constant remainder (with view by telescopy)

Question

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

Answer 1

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

Answer 2

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

Answer 3

The induction step should be $\,12\mid a_n-7\Rightarrow 12\mid a_{n+1}-7,\,$ which is arithmetically clearer in modular language, namely: $\!\bmod 12\!:\ a_n\equiv 7\Rightarrow a_{n+1}\equiv 7,\,$ so we may apply the following

Key Idea a sequence $\,a_n\,$ is constant $\,a_n\equiv a_0\ [\equiv 7]\,$ if it $\color{#c00}{\text{never changes value,}}$ by below.

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 all $\,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. $\,\small\bf QED$

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

---

Remark $\ $ We may view this as special case of telescopy since we can write $\,a(n) = a_n\,$ as a telescoping sum of 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.

---

Below is another example from a deleted question which explicitly shows the induction schema.

I was going through my textbook and I found that when you're proving divisibility for a function $f(n)$, one approach is to use $f(k+1) - f(k)$ but it doesn't explain why it works. I haven't been able to figure out why and how this allows us to prove that a function $f(n)$ is divisible by an integer $r$. What is the intuition or reasoning behind this?

Likely you mean the telescopic induction schemas below, in divisibility & congruence form: $$ \bbox[1px,border:3px solid #c60]{\bbox[8px,border:1px solid #c00]{\forall\, n\ge 0\!:\ \ d\ |\ f_n \iff {\bf \large [}\,d\ |\ f_0\ \ \& \ \ \forall\, n\ge 0\!:\ d\ |\ \color{#0a0}{f_{\,n+1}\!-f_n}\,{\bf \large ]}}}\quad $$

$$ \bbox[1px,border:3px solid #c60]{\bbox[8px,border:1px solid #c00]{\forall\, n\ge 0\!:\, f_n\equiv_{_{\large d}} c\!\iff\! {\bf \large [}\:\! f_0\equiv_{_{\large d}} c\ \ \&\,\ \forall\, n\ge 0\!:\,\ \color{#0a0}{f_{\,n+1}\!\equiv_{_{\large d}} f_n\:\!}{\bf \large ]}}\:\!}\quad $$

Notice it is more intuitive in congruence language: if the value of $f$ never changes at successive integers $\,\color{#0a0}{n,\,n\!+\!1},\,$ then $\!\bmod d\!: f\:\!$ is constant so $\,f_n\equiv f_0\equiv c\ $ ($c\!=\!0$ in the first schema).

Notice the inductive step is trivial: $ $ if $\,f_k\equiv c\,$ then $\,\color{#0a0}{f_{k+1}\equiv f_k}\equiv c\,\ $ [for the direction $\Leftarrow$]

Viewed as a telescoping sum: $\,f_n = f_0 + \sum_{k=0}^{n-1} (\color{#0a0}{f_{k+1}\!-f_k})\equiv f_0\,$ by all $\,\color{#0a0}{f_{k+1}\!-f_k}\equiv 0$.

The reason this method often simplifies such inductive proofs is because the first difference $\,\color{#0a0}{f_{n+1}\!-f_n}\,$ is degree reducing in the common case when $\,f_n\,$ is a polynomial in $\,n,\,$ so the degree reduction simplifies the problem. For many worked examples see here and its links.

---

From here is a simple example: $\!\bmod 8\!:\ {\rm odd}^2\equiv 1,\,$ i.e. $\,f_n = (2n\!-\!1)^2\equiv 1\,$ is true because $\,f_{n+1}-f_n = (2n\!+\!1)^2-(2n\!-\!1)^2\! = \color{#0a0}{8n}\equiv 0,\,$ so $\,f_n\equiv \color{#c00}{f_0\equiv \bf 1}\,$ by the 2nd schema above.

The telescoping sum form of the above inductive proof is simply

$$ (2n-1)^2 = \color{#c00}{\bf 1} + \sum_{k\,=\,1}^{n-1}\!\: \color{#0a0}{8k}\,\equiv\, 1\!\!\!\pmod{\!\color{#0a0}8}\qquad$$