proving the divisibility rule for 11 using induction

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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