# proving the divisibility rule for 11 using induction

I'm trying to prove the divisibility rule for 11: $(11 | (10^n + (-1)^{n+1})$ via induction, and I'm stuck.

I started with a base case of 0, and made my inductive hypothesis:

$(11 | (10^k + (-1)^{k+1})$

And my inductive step was:

$(11 | (10^{k+1} + (-1)^{k+2})$

I rewrote my hypothesis as $11 = s * (11 | (10^k + (-1)^{k+1})$, where s is an element of the integers

then my inductive step as $11 = s * (11 | s * (10^{k+1} + (-1)^{k+2})$

I've tried substituting multiple parts in from my inductive step, but I'm still stuck. Any help is appreciated, thanks!

• "The" divisibility rule $11\mid 10^n+(-1)^{n+1}$? Are you sure that's the the division you're trying to prove? Also, this problem is trivial if you look $\mod 11$ - no need for induction – vrugtehagel Mar 24 '17 at 17:53
• That is the rule I'm trying to prove, and I am intentionally solving this via induction, I'm aware there are simpler methods – Howard P Mar 24 '17 at 17:58
• Hem, are you sure that $11|10^0+(-1)^1$ ?? – Yves Daoust Mar 24 '17 at 18:17
• In that case, we have 11 | 0, which is true – Howard P Mar 24 '17 at 18:26

First of all,

$$11 = s * (11 | (10^k + (-1)^{k+1})$$

doesn't make any sense. The line in $a\mid b$ is not an operator; it shows a relation between $a$ and $b$. You can't multiply a number by a relation.

You probably wanted to write

$$10^k + (-1)^{k+1}=11\cdot s$$

as hypothesis, and then

\begin{align} 10^{k+1} + (-1)^{k+2}&=10^{k+1}+10\cdot(-1)^{k+1}-10\cdot(-1)^{k+1}+(-1)^{k+2}\\ &=10\cdot(10^k+(-1)^{k+1})+(-1)^{k+1}(-10+-1)\\ &=10\cdot 11\cdot s-(-1)^{k+1}\cdot11\\ &=11\cdot(10s-(-1)^{k+1}) \end{align} Is the induction step. This, with your base case, completes the proof.

• Thank you for correcting me on that one, was thinking too hard. – Howard P Mar 24 '17 at 18:28

let $$T_k=10^ki+(-1)^{k+1}$$ and $$11|T_k$$ and we define $$T_{k+1}=10^{k+1}+(-1)^{k+1}$$ then we get $$T_{k+1}-T_k=10^k\cdot 9-2\cdot (-1)^{k+1}=11\cdot 10^k-2((10^k+(-1)^{k+1})$$ the right-hand side our equation is divisible by $$11$$ and $$T_k$$ is divisble by $$11$$ thus $$11$$ is a divisor of $$T_{k+1}$$

Notice $10^{k+1} + (-1)^{k+2} =$

$10(10^{k} + (-1)^{k+1}) - 10(-1)^{k+1} + (-1)^{k+2} =$

$10\color{red}{(10^{k+1} + (-1)^{k})} - 10(-1)^{k+1} + (-1)(-1)^{k+1} =$

$10\color{red}{(10^{k+1} + (-1)^{k})} - 10(-1)^{k+1} - (-1)^{k+1} =$

$10\color{red}{(10^{k+1} + (-1)^{k})} - 11(-1)^{k+1} =$

$11[\frac{\color{red}{(10^{k+1} + (-1)^{k})}}{11} - (-1)^{k+1}]$