Friday, March 24, 2017

proof writing - 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.


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...