Proof by Induction Problem

Question

I need to prove that for natural numbers $a$, and positive integers $n$, the number $a^{2n+1}-a$ is divisible by $6$.

I have proved the case when $n=1$, that $a^3-a$ is divisible by $6$. I'm having trouble proving that if $a^{2n+1}-a$ is divisible by $6$, then $a^{2(n+1)+1}-a$ is also divisible by $6$.

Answer 1

hint: $a^{2n+1} - a = a(a^{2n}-1) = a(a^2-1)(a^{2n-2} + a^{2n-4} + \cdots + 1) = a(a-1)(a+1)(.....)$ is divisible by $6$ since it has a product of $3$ consecutive integers: $a-1,a,a+1$.

To do an induction proof.

The base case is done. Assume $6\mid a^{2n+1} - a \Rightarrow a^{2n+3} - a = (a^{2n+3} - a^{2n+1}) + (a^{2n+1} - a) = a^{2n}\cdot a\cdot (a-1)(a+1) + (a^{2n+1}-a)$ is divisible by $6$ since the first term has again a product of $3$ consecutive integers, and the expression in the parentheses is divisible by $6$ by inductive step so the sum is divisible by $6$, complete the induction proof.

Answer 2

Induction assumption: $a^{(2n+1)} \equiv a \pmod 6$. OK, we prove this for n=1, and then we assume this is true for n.

Now we have: $a^{(2n+3)} \pmod 6\equiv (a^{(2n+1)}) * (a^2) \pmod 6 \equiv $ (using the induction hypothesis) $ \equiv a \cdot a^2 \pmod 6\equiv a^3 \pmod 6$

But $a^3 - a = a\cdot(a-1)\cdot(a+1) $ which is apparently divisible by 6 (because this product contains 1 number divisible by 2 and one number divisible by 3). Thus $6 / (a^3 - a)$ and therefore $6 / (a^{(2n+3)}-a)$

Answer 3

Hint $\ $ Let $\,f(n) = a^{2n+1}\!-a\,$ Then $\,f(n\!+\!1) - f(n)= (a\!-\!1)a(a\!+\!1) a^{2n}\,$ is a multiple of $6,\,$ since a product of $3$ consecutive integers is divisible by both $3$ and $2.\,$ Therefore if $\,f(n)\,$ is divisible by $6$ then so too is $\,f(n\!+\!1) = f(n) + (a\!-\!1)a(a\!+\!1)a^{2n},\,$ yielding the inductive step.

Remark $\ $ The method employed is a very general one that is worth explaining. The basic idea is that $\,6\,$ dividies $\,f(n)\,$ for all $\,n\ge 0\,$ iff it is the constant sequence $\,f(n)\equiv 0\pmod 6.$ But it is trivial to prove by induction that a sequence has constant value $\equiv c\,$ $\iff$ $\,f(0)\equiv c\,$ and $\,f(n\!+\!1)\equiv f(n),\,$ i.e. $\,f(n\!+\!1)-f(n)\equiv 0.\,$ This is precisely the method employed above, except it uses divisibility language vs. modular language (congruences).

This method is a special case of the powerful method telescopic induction, which is explained at length in many posts here.

Answer 4

Hint: $a^{2n+3}-a = a^2 ( a^{2n+1} -a ) + (a^3 -a )$.

Answer 5

You've shown that this is true for $n=1$:

$a^{2+1}-a=6m$

Assume that this is true for $n$:

$a^{2n+1}-a=6k$

Prove that this is true for $n+1$:

$a^{2(n+1)+1}-a=$

$a^{2n+3}-a=$

$a^2(a^{2n+1}-a)+a^3-a=$

$a^2(\color{red}{a^{2n+1}-a})+\color{blue}{a^{2+1}-a}=$

$a^2\color{red}{6k}+\color{blue}{6m}=$

$6(a^2k+m)$

---

Please note:

• The base-case is used in the part marked blue
• The assumption is used in the part marked red

Answer 6

Since you have proved $a^3-a$ is divisive by $6$ that is $a^3-a=6q_1$ where $q_1\in\mathbb{Z}.$ If $a^{2n+1}-a$ is divisible by $6,$ then $a^{2n+1}-a=6q$ where $q\in \mathbb{Z}.$ This implies $a^{2n+1}=6q+a,$ equivalently $a^{2n+3}=6qa^2+a^3$ or $$a^{2n+3}-a=6qa^2+a^3-a=6qa^2+6q_1=6(qa^2+q_1)$$ That is $a^{2n+3}-a$ is divisible by 6.