5
$\begingroup$

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$

I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the completely wrong direction? Any help would be appreciated.

$\endgroup$
4
  • 7
    $\begingroup$ $10^{2k+2}-1=10^2(10^{2k}-1)+10^2-1$. $\endgroup$ Mar 7 '15 at 1:46
  • 1
    $\begingroup$ @AndréNicolas: I have no idea how I would've thought of that. Thank you very much. $\endgroup$
    – Bob
    Mar 7 '15 at 2:10
  • 1
    $\begingroup$ You are welcome. If one works with induction on exponentials, tricks of this general kind become familiar. $\endgroup$ Mar 7 '15 at 2:16
  • 1
    $\begingroup$ In my answer I show how you can discover the proof of @André and oujdid, by a mechanical method. $\endgroup$ Mar 7 '15 at 5:05
9
$\begingroup$

In a comment you remark that you have no idea how Andre thought of the inductive proof. Below we will show that it is not a magic trick but, rather, a special case of a simple general method that works for inductions of this type. Below 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 equivalent $\rm\color{#0a0}{divisibility\ form}$. Recall that $\rm\ n\mid k\,$ means $\rm\,n\,$ divides $\rm\,k.\,$

$\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 above, i.e. $\,{\rm mod}\ 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).

$\endgroup$
2
  • $\begingroup$ And, as an instance, note that the usual proof of the calculus Product Rule uses the same device. $\endgroup$ Mar 7 '15 at 5:18
  • $\begingroup$ @André Indeed, I write about that here (too briefly) $\endgroup$ Mar 7 '15 at 5:24
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ If you observe that, it's finished with congruences, without any induction. $\endgroup$
    – Bernard
    Mar 7 '15 at 1:49
  • 1
    $\begingroup$ Did you mean $10^{2k+2}-1$ as the left side? $\endgroup$ Mar 7 '15 at 1:51
  • $\begingroup$ it's really easy so using induction or congruence yields the result, but he pointed that he is trying to prove it by induction so i'm supposed to follow his work not to ignore what he did $\endgroup$
    – user217773
    Mar 7 '15 at 2:07
  • $\begingroup$ @Bernard In my answer I show that this proof is a special case of the proof of the Congruence Product Rule. $\endgroup$ Mar 7 '15 at 5:38
3
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Simpler solution inspired by Bill's answer. $\endgroup$
    – copper.hat
    Mar 7 '15 at 5:36
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

For $n = 1$, $10^{2n}-1 = 99$, which is divisible by $11$. Let us assume that the given statement is true for $n = m$, i.e. $10^{2m}-1$ is divisible by $11$. Now, $10^{2m+2}-1 = 10^{2m}\times 100-1 = 10^{2m}\times (11\times 9 + 1) - 1 = (10^{2m}\times 11\times 9) + 10^{2m}-1$. But $10^{2m}-1$ is divisible by $11$. So the result follows.

$\endgroup$
1
$\begingroup$

A variant for the induction: suppose the assertion true for all $k\le n$ and let's prove it for $n+1$. We have: $$10^{2(n+1)}-1=(10^{n+1}-1)(10^{n+1}+1)$$ If $n$ is even, $n+1$ is odd, and $10^{n+1}+1\,$ is divisible by $10+1$.

If $n$ is odd, write $n=2l-1$; Then $$10^{2(n+1)}-1=10^{4l}-1=(10^{2l}-1)(10^{2l}+1) $$ and $10^{2l}-1$ is divisible by $11$ by the inductive hypothesis.

$\endgroup$
0
$\begingroup$

Ok this is not a strict inductive proof. More like an algorithmic proof or something.

Conjugate rule $a^2 - b^2 = (a+b)(a-b)$, $a = 10^n$, $b = 1$,

1) if $n$ even continue with conjugate rule on the factor $a-b$ which is on the same form,

2) once $n$ is odd , write term $a+b = 10^{2k+1}+1$ and take mod 11, $(-1)^{2k+1} + 1 = 0 (mod 11)$ for all integers $k$.

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