# Prove by induction that $10^n -1$ is divisible by 11 for every even natural number

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number n. $0 \notin N$

Base Case: n = 2, since it is the first even natural number. $10^2 -1 = 99$ which is divisible by 11.

Assume $n =k$ is true for some $k \in N$. Now prove $n=k+1$ is true.

$10^k -1$

I know I have to put k+1 instead of k, but I do not know how to relate the induction hypothesis with k+1.

HINT:

If $f(n)=10^n-1$

$f(n+2)-f(n)=10^n(10^2-1)\equiv0\pmod{11}$

So, $f(n+2)$ will be divisible by $11$ if $f(n)$ is divisible by $11$

What is the base case $n=2,$ i.e, $f(2)$

Hint With a strong induction (assume the result true for $n-1$)

For $n+1$: $$10^{n+1}-1=10^2(10^{n-1}-1)+9\times 11$$

• Your equality is off by 2 ;) – N. S. Dec 13 '13 at 18:55
• @Sami where did you get 11 – Mac Dec 13 '13 at 18:58

Hint: $100^{k+1}-1 = 100^{k+1} - 100^{k} + 100^{k} -1$

Write $n=2k$. Then, you need to prove by induction that $11|10^{2k}-1$. Do induction by $k$.

Otherwise, if you want to do induction by $n$, note that if $n$ is even, the next even number is $n+2$. Your inductive step should be

$$P(n) \Rightarrow P(n+2)$$

• Would the downvoter please explain? – N. S. Dec 17 '13 at 2:17
• Why downvote without any alarm??!! – mrs Jan 25 '14 at 18:01

As $n$ is even we can write it as $n=2k$

$$10^n-1=10^{2k}-1 =-1^{2k}-1 \text{ As } 10= -1\bmod{11}$$ And $-1$ raised to even integer$=1$ Therefore,$=1-1=0$ Hence,proved