1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ "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 $\endgroup$ – vrugtehagel Mar 24 '17 at 17:53
  • $\begingroup$ That is the rule I'm trying to prove, and I am intentionally solving this via induction, I'm aware there are simpler methods $\endgroup$ – Howard P Mar 24 '17 at 17:58
  • 1
    $\begingroup$ Hem, are you sure that $11|10^0+(-1)^1$ ?? $\endgroup$ – Yves Daoust Mar 24 '17 at 18:17
  • $\begingroup$ In that case, we have 11 | 0, which is true $\endgroup$ – Howard P Mar 24 '17 at 18:26
1
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.