2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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

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

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

$\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.