Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

Solution 1:

In a comment you remark that you have no idea how Andre thought of the inductive proof. Below we show that it is a special case of a simple general method that works for inductions of this type. We show extremely explicitly how the inductive steps in the proofs by Andre and oujdid are both precisely special cases of proofs of the Congruence Product Rule. You need not be familiar with congruences to understand this since we also write it in an equivalent $\rm\color{#0a0}{divisibility\ form}$.

$\!\!\begin{align} {\bf Claim}\rm\qquad\ \ 10^2\!&\rm\equiv 1, \, 10^{2k}\!\equiv 1\ \, \Rightarrow\,\ 10^{2(k+1)}\!\equiv 1\, \pmod{\!11}\\[.3em] {\bf Lemma}\rm\qquad\ A&\rm\equiv a,\ \, B\equiv b\quad \Rightarrow\quad\,\ AB\equiv ab\, \pmod{\!n}\ \ \ \ [\rm\color{#c00}Congruence \ \rm\color{#c00}Product\ \rm\color{#c00}Rule]\\[.3em] \rm\quad\ \ i.e.\quad\! n\mid A&\rm -a,\ \ B\,-\,b\ \Rightarrow\,\ n\mid \,AB\,-\,ab\qquad\qquad\ \ \ \ \ \ \:\! [\rm\color{#c00}{CPR}\ in\ \color{#0a0}{divisibility\ form}]\\[.5em] {\bf Proof}\quad\ \ \ \rm n\mid A&\rm -a,\ \ B\,-\,b\,\Rightarrow\,\ n\mid \ A\ (\ B\,-\,b)+\,(\ A-a)b\, =\ \,A\, B\,-\,a\,b\\[.3em] \rm\quad\ e.g.\,\ 11\mid 10^2&\rm -\!1,\ 10^{2k}\!-\!1\,\Rightarrow 11\mid\! 10^2(10^{2k}\!-\!1)+(10^2\!-\!1)1\,= 10^{2(k+1)}\!-1\ \ \ [Andre]\\[.5em] {\bf Proof}\quad\ \ \ \rm n\mid A&\rm -a,\ \ B\,-\,b\,\Rightarrow\,\ n\mid (\, A-a)\,\ B\ \ +a\ (\ B-b)\, =\ \,A\, B\,-\,a\,b\\[.3em] \rm\quad\ e.g.\,\ 11\mid 10^2&\rm -\!1,\ 10^{2k}\!-\!1\,\Rightarrow 11\mid(10^2\!-\!1)10^{2k}\!+\! 1(10^{2k}\!\!-\!1) = 10^{2(k+1)}\!-1\ \ \ [oujdid] \end{align}$

So the inductive steps of Andre and oujdid - which appear to have been pulled out of hat like magic - are actually nothing but special cases of the proofs of $\,\small \rm\color{#c00}{CPR} = $ Congruence Product Rule. Once we know this rule, there is no need to repeat the entire proof inline every time that we employ it. Rather, we can simply invoke the rule as a Lemma (in $\rm\color{#0a0}{divisibility\ form}$ if congruences are not yet known). That done, the inductive step has vivid arithmetical structure, being simply the computation of a product $\, 10^2\!\cdot 10^{2k}\equiv 10^{2(k+1)}.\,$ No longer is the innate arithmetical structure of the induction obfuscated by the details of the proof of the Product Rule - since the proof has been encapsulated into a Lemma for convenient reuse.

In much the same way, congruences often allow us to impart intuitive arithmetical structure onto inductive proofs - allowing us to reuse our well-honed grade-school skills manipulating arithmetical equations (vs. more complex divisibility relations). Often introduction of congruence language will serve to drastically simplify the induction, e.g. reducing it to a trivial induction such as $\, 1^n\equiv 1,\,$ or $\,(-1)^{2n}\equiv 1,\,$ which is the essence of the inductive proof above, i.e. $\!\bmod 11\!:\,\ 10\equiv -1\,\Rightarrow\,10^{2n}\equiv (-1)^{2n}\equiv 1\,$ by the Congruence Power Rule, whose proof is an immediate inductive extension of the Product Rule exactly as in the proof of above OP special case. In number theory we typically make such inferences by applying the Power Rule (or the more general Polynomial Congruence Rule, i.e. $\,a\equiv b\,\Rightarrow\, P(a)\equiv P(b)\,$ for any polynomial $P(x)$ with integer coefficients).

Solution 2:

Hint did you observe that $10^2=99+1$ so you can write: $$10^{2k+2}-1=99.10^{2k}+10^{2k}-1 $$

and apply the iduction hypothesis

Solution 3:

One really doesn’t need induction for this:

$$\begin{align*} 10^{2n}-1&=\underbrace{999999\ldots999999}_{2n\text{ nines}}\\ &=\underbrace{99\,99\,99\,\ldots\,99\,99\,99}_{n\text{ copies of }99}\\ &=11\cdot\underbrace{09\,09\,09\,\ldots\,09\,09\,09}_{n\text{ copies of }09}\\ &=11\cdot 9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}\;. \end{align*}\tag{1}$$

However, if you’re required to use induction you can use the calculation above to work out what should happen in the induction step. It’s pretty clear from $(1)$ that $10^{2n+2}-1$ is going to be $11$ times the number formed by a $9$ followed by $n$ copies of $09$:

$$\begin{align*} 10^{2n+2}-1&=11\cdot 9\underbrace{090909\ldots090909}_{n\text{ copies of }09}\\ &=11\cdot 9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}09\\ &=11\left(100\cdot9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}+9\right)\\ &=100\cdot11\cdot9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}+11\cdot9\\ &=100\left(10^{2n}-1\right)+11\cdot 9\;, \end{align*}$$

so if $10^{2n}-1$ is a multiple of $11$, so is $10^{2n+2}$.

Now you can clean up the induction step by eliminating all of the explicit decimal representations and going directly (or nearly so) from $10^{2n+2}$ to $100\left(10^{2n}-1\right)+11\cdot9$; the digit-tracking can then be regarded as simply a way to figure out what’s going on.

Solution 4:

Just in case, a solution without induction (or at least any induction is buried somewhere):

We have $[10]_{11} = [-1]_{11}$, and so $[10^{2n}]_{11} = [(-1)^{2n}]_{11} = [1]_{11}$

Then $[10^{2n}-1]_{11} = 0$ and so $11 \mid 10^{2n}-1$.

Notation: $[a]_b = a+b \mathbb{Z}$.

Solution 5:

First, show that this is true for $n=1$:

$10^{2}-1=11\cdot9$

Second, assume that this is true for $n$:

$10^{2n}-1=11k$

Third, prove that this is true for $n+1$:

$10^{2(n+1)}-1=$

$10^{2n+2}-1=$

$100(10^{2n})-1=$

$100(\color{red}{10^{2n}-1})+99=$

$100(\color{red}{11k})+99=$

$11(100k+9)=$

Please note that the assumption is used only in the part marked red.