Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To prove $10^n \equiv (-1)^n\pmod{11}$, $n\geq 0$, I started an induction.

It's $$11|((-1)^n - 10^n) \Longrightarrow (-1)^n -10^n = k*11,\quad k \in \mathbb{Z}. $$

For $n = 0$: $$ (-1)^0 - (10)^0 = 0*11 $$

$n\Rightarrow n+1$ $$\begin{align*} (-1) ^{n+1} - (10) ^{n+1} &= k*11\\ (-1)*(-1)^n - 10*(10)^n &= k*11 \end{align*}$$ But I don't get the next step.

share|improve this question

12 Answers 12

You are not setting up your induction very well. You should not start with the equality you want to establish, namely that $(-1)^{n+1}-10^{n+1}$ is a multiple of $11$. Instead, you should start with the Induction Hypothesis, which is that $(-1)^n - 10^n$ is a multiple of $11$.

So: the Inductive Step is to show that if $(-1)^n - 10^n$ is a multiple of $11$, then $(-1)^{n+1} - 10^{n+1}$ is also a multiple of $11$.

Let's write out our Induction Hypothesis: it says that $$\text{There exists an integer }k\text{ such that }(-1)^n - 10^n = 11k.$$

What we want to prove is that: $$\text{there exists an integer }\ell\text{ such that }(-1)^{n+1}-10^{n+1}=11\ell.$$ (Note that the multiple may be different, that's why I used a different letter).

So now we can try manipulating the expression we want. One possibility is to use the following identity: $$a^{n+1}-b^{n+1} = (a-b)(a^n + a^{n-1}b + a^{n-2}b^2 + \cdots + ab^{n-1}+b^n),$$ if you already know this identity.

So we have, with $a=-1$ and $b=10$, $$ (-1)^{n+1} - 10^{n+1} = \Bigl( (-1) - 10\Bigr)\Bigl( (-1)^n + (-1)^{n-1}(10) + \cdots + (-1)10^{n-1} + 10^n\Bigr).$$ Now notice that you don't even need to use the induction hypothesis to conclude that $(-1)^{n+1}-10^{n+1}$ is a multiple of $11$ (as could be seen in mac's answer).

If you don't know the identity, then you can perform some purely algebraic manipulations. E.g., $$\begin{align*} (-1)^{n+1} - 10^{n+1} &= -1\left( (-1)^n + 10^{n+1}\right)\\ &= -\left( (-1)^n -10^n + 10^n + 10^{n+1}\right)\\ &= -\left( \Bigl((-1)^n - 10^n\Bigr) + 10^n\Bigl(1 + 10\Bigr)\right)\\ &= -\left( 11k + 10^n(11)\right) &\quad&\text{(by the induction hypothesis)}\\ &= -\left( 11(k+10^n)\right)\\ &= 11\left( -(k+10^n)\right), \end{align*}$$ which gives that $(-1)^{n+1} - 10^{n+1}$ is a multiple of $11$, as desired, from the assumption that $(-1)^n - 10^n$ is a multiple of $11$.


But easier still is to use the following property of congruences:

Proposition. Let $a,b,c,d,k$ be integers. If $$a\equiv b\pmod{k}\qquad\text{and}\qquad c\equiv d\pmod{k}$$ then $ac\equiv bd\pmod{k}$.

Proof. Since $a\equiv b\pmod{k}$, then $k|a-b$, so $k$ divides any multiple of $a-b$; for example, $k|(a-b)c = ac-bc$. Since $k$ divides $ac-bc$, then $ac\equiv bc\pmod{k}$.

Since $c\equiv d\pmod{k}$, then $k|c-d$, so $k|(c-d)b = cb-db$, hence $bc\equiv bd\pmod{k}$.

Since $ac\equiv bc\pmod{k}$ and $bc\equiv bd\pmod{k}$, then $ac\equiv bd\pmod{k}$. QED

Corollary. If $a_1\equiv b_1\pmod{k}$, $a_2\equiv b_2\pmod{k},\ldots, a_n\equiv b_n\pmod{k}$, then $$a_1\cdots a_n\equiv b_1\cdots b_n\pmod{k}.$$

Proof. Induction on $n$. QED

(This is where you would want to use induction, rather than the specific case you are looking at).

Corollary. If $a\equiv b\pmod{k}$, then for all positive integers $n$, $a^n\equiv b^n\pmod{k}$.

Proof. Apply previous corollary with $a_i=a$ and $b_i=b$ for all $i$. QED

share|improve this answer
    
@Arturo One needs to be careful here. The first proof could well be circular. You are apparently implicitly assuming the result that for all $\rm\:n\:$ one has $\rm\ a-b\ |\ a^n - b^n\ $ in $\rm\:\mathbb Z[a,b]\:,\:$ which is stronger than the result desired and, moreover, it requires an (inductive) proof itself (at this level). One could perhaps work around this if it could be deduced as a special case of some more general known result, such as the Factor Theorem $\rm\:x-y\ |\ f(x)-f(y)\:,\:$ but I don't see any mention of such above, nor is it clear that the OP has access to such. –  Bill Dubuque May 18 '11 at 18:37
    
@Bill: Technically, I'm asserting an equality between $a^{n+1}-b^{n+1}$ and $(a-b)(a^n + a^{n-1}b+\cdots+ab^{n}+b^{n+1})$, which implies the divisibility statement you say I am "implicitly assuming"; I grant that I'm not proving that assertion (which can be done by induction), but seems somewhat askew to say I'm "implicitly assuming" a result when I am explicitly saying what I'm using. –  Arturo Magidin May 18 '11 at 18:47
    
@Arturo: If you're assuming that (much stronger) result without proof then the proof is circular in my opinion. Moreover, I don't think it is good from a pedagogical standpoint to manipulate expressions involving '$\:\ldots\:$' when teaching inductive proofs. The whole point of mathematical induction is to eliminate such nonrigorous inductive informalities in favor of objects with more rigorous syntax and semantics. –  Bill Dubuque May 18 '11 at 18:58
    
@Bill: I am well aware that your geometric notions and mine don't agree. –  Arturo Magidin May 18 '11 at 18:59
    
@Bill: You missed the joke. I'm well aware that what I consider "circular" and what you consider "circular" (i.e., "geometric notions") are not the same thing. I'm also well aware that you often call things I do "circular" on the basis of what you consider to be "previous", "stronger", etc., and that I don't always agree. But, please, do go ahead expressing how disappointed you are; it's not my goal to please you. –  Arturo Magidin May 18 '11 at 19:01

If you want to use induction you assume that $(-1)^n-10^n=11k$ Then you want to prove $(-1)^{(n+1)}-10^{(n+1)}=11m$. So $(-1)^{(n+1)}-10^{(n+1)}=-1(-1)^n-10(10^n)=-1(11k+10^n)-10(10^n)=-11k-11(10^n)=11m$

share|improve this answer

Since 10 ≡ -1 (mod 11), you can just raise both sides to the power of $n$.

share|improve this answer
    
Hi, I was thinking something similar to this, but what's the mathematical explanation for that? –  Igor May 18 '11 at 16:44
    
Well, $$a_1\equiv b_1\pmod k,\quad a_2\equiv b_2\pmod k\implies a_1a_2\equiv b_1b_2\pmod k.$$ So by (a very easy) induction on $n$, $a\equiv b\pmod k\implies a^n\equiv b^n\pmod k$. The proof of the implication above isn't so hard: the hypothesis is the same as $k|a_1-b_1$ and $k|a_2-b_2$, hence $k|(a_1-b_1)a_2+b_1(a_2-b_2)=a_1a_2-b_ab_2$. –  mac May 18 '11 at 16:47
    
@Igor: The explanation is that if $k$ divides $a-b$, then $k$ divides $(a-b)c = ac-bc$, so from $a\equiv b\pmod{k}$ you can conclude that $ac\equiv bc\pmod{k}$. Starting from $x\equiv y\pmod{k}$ and $z\equiv w\pmod{k}$, multiplying both sides of $x\equiv y\pmod{k}$ by $z$ we get the valie $xz\equiv yz\pmod{k}$. Multiplying both sides of $z\equiv w\pmod{k}$ by $y$ we get $zy\equiv wy\pmod{k}$. Putting the two together, we get $xz\equiv yz\equiv yw\pmod{k}$. So if $x\equiv y\pmod{k}$ and $z\equiv w\pmod{k}$, then $xz\equiv yw\pmod{k}$ (that is, you can multiply congruences). –  Arturo Magidin May 18 '11 at 16:51
    
Hm, I can't seem to correct my earlier comment any more. It should be $b_1$, not $b_a$ at the end. –  mac May 18 '11 at 16:54
    
@Igor The "mathematical explanation" is the congruence product rule - see my answer. Or, more generally, that the set of congruence classes comprise a ring $\rm\:\mathbb Z/11 = \mathbb Z\ (mod\ 11)\:.$ –  Bill Dubuque May 18 '11 at 17:34

Below are some general remarks on inductive proofs that are too long for comments. The primary point that I'd like to emphasize is that when you are first learning how to present rigorous proofs by mathematical induction it is important to be careful to avoid composing circular proofs. Let's consider a specific example. In another answer here a proof of the desired result, that $\rm\ 10^n\equiv (-1)^n\ (mod\ 11)\:,\:$ was proposed based upon the following identity, which is true for all integers $\rm\:a,b\:$ and all naturals $\rm\:n\:$

$$\rm a^{n+1}-b^{n+1}\ =\ (a-b)\ (a^n + a^{n-1}b + a^{n-2}b^2 + \cdots + ab^{n-1}+b^n) $$

The sought result follows immediately upon specializing $\rm\: a = 10,\: b = -1\:$ in the above identity.

Does the above constitute a valid proof by induction of the sought result? Probably your instructor would accept it as a valid proof if you first proved by induction said identity and then derived the sought result as a corollary, by specializing the identity as indicated above. However, if you don't already have available a rigorous proof that the above identity holds true for all $\rm\:n\:$ then it would not be correct to invoke the identity in your proof since, in effect, you would be assuming true a more general result, that itself requires a rigorous proof by induction. Even though you may have learned this identity in your prior studies, before you learned how to give rigorous inductive proofs, probably at that time you did not have available the tools to give such a rigorous proof. Perhaps you may even have learned more general results, such as the Factor Theorem $\rm\ x-y\ |\ f(x)-f(y)\:$ in $\rm\:\mathbb Z[x,y]\:$ for all polynomials $\rm\:f(x)\in\mathbb Z[x]\:.\:$ But this too requires a rigorous inductive proof, e.g. by induction on $\rm\: deg\ f\:.\:$

Thus if you propose to tackle an exercise on induction by "passing the inductive buck" to a more general result, be sure that you have already given a rigorous inductive proof of that result. Since the point of such exercises is to provide experience to help strengthen your inductive intuition, it is essential to experience the induction - whether in a specific form or a more general form.

Once you have gained some experience with inductive proofs it is important to introspect a bit at a meta-level - to abstract out various common patterns of induction. For example, many of my posts here emphasize the fact that many common inductive proofs are simply special cases of telescopy. By noticing this telescopic structure, one can often reduce the induction to a very trivial normalized form, e.g. to the trivial induction that $\rm\: 1^n = 1\:.\:$ Such reduction of inductive complexity frees up our mental faculties so that we can concentrate on more essential aspects of the problem.

share|improve this answer
    
Idea of "telescopy" sounds interesting — do you have some reference, by any chance? –  Grigory M May 23 '11 at 11:52
    
@Grigory Off the top of my head I can't recall any references specific to induction. But, at the core, it's just a special case of effective algorithms for summation and solving difference equations, e.g. Google Gosper, Karr, Singer, Zeilberger, etc. There are many simple examples in my prior posts in the link above. –  Bill Dubuque May 23 '11 at 11:58

If $a \equiv b \left(\bmod m \right)$, then $a^n \equiv b^n \left(\bmod m \right)$ where $n \in \mathbb{N}$ and $a,b,m \in \mathbb{Z}$.

The reason being $a^n - b^n$ factors as $(a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \cdots + b^{n-1})$ and hence if $m | (a-b)$, $m | (a^n-b^n)$

If you want to prove by induction, first note that

if $a \equiv b \left(\bmod m \right)$ and $c \equiv d \left(\bmod m \right)$, then $a \times c \equiv b \times d \left(\bmod m \right)$.

This is true since $ac-bd = a(c-d) + d(a-b)$

Hence at the inductive step, if you have that $10^k \equiv (-1)^k \left(\bmod m \right)$, and we have that $10 \equiv (-1) \left(\bmod m \right)$ and from the above result we have $$10^{k+1} \equiv (-1)^{k+1} \left(\bmod m \right)$$

share|improve this answer

Why don't you try this: $10 \equiv -1 \ (\text{mod} \ 11) \Longrightarrow (10)^{n} \equiv (-1)^{n} \ (\text{mod} \ 11)$

  • And for using induction assume it's clear that for $n=1$, the result holds. Now assume that is true for $n=k$. That is $(10)^{k} \equiv (-1)^{k} \ (\text{mod} \ 11)$, and prove it for $n=k+1$.
share|improve this answer

Might be easier to do $P(n) \Rightarrow P(n+2)$, i.e. prove it for odd and even numbers separately.

$P(1), P(2)$ are clear.

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

$$10^{n+2}= 10^n*100=99*10^n+10^n \cong 10^n \cong (-1)^n \mod 11$$

share|improve this answer

HINT $\ $ The inductive step is $\rm\ 10\:\equiv\: -1,\ 10^n\:\equiv\: (-1)^n\ \ \Rightarrow\ \ 10^{n+1}\:\equiv\: (-1)^{n+1}\ \ (mod\ 11)\:.\ $

This is simply a special case of the following ubiquitous rule for multiplying congruences

Congruence Product Rule $\rm\ \ A\equiv\: a,\ B\:\equiv\: b\ \ \Rightarrow\ \ AB\equiv ab\ \ \ (mod\ m)$

Proof $\rm\ \ m\ |\ A-a,\: B-b\ \ \Rightarrow\ \ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $

You can find much further discussion of this fundamental product rule in many of my prior posts. For example, this post explains how the derivative product rule is closely related to the congruence product rule. See also this post which explains the relationship between arithmetic divisibility rules and subring structure. Many of these diverse topics will be unified when you learn about quotient rings, a ubiquitous prototype being the ring $\rm\:\mathbb Z/m\:$ of integers modulo $\rm\:m\:.$

share|improve this answer

And since noone mentioned this yet, here is a direct proof.

If $n=2k$ is even we need to show that $10^n \cong 1 \mod 11$. But $10^{2k}-1=999....999$ where there are $2k$ 9's. Thus

$$10^{2k}-1= 90909090..909 *11 $$

If $n=2k+1$ is even we need to show that $10^n \cong -1 \mod 11$.

But $10^{2k+1}+1=999....9990+11$ where there are $2k$ 9's. Thus

$$10^{2k}+1= 90909090..9090 *11 +11$$

Second direct solution

We will prove instead that

$$(-10)^n \equiv 1 \pmod{11}

using the well known geometric formula:

$$1-10+10^2-10^3+...+(-10)^{n-1}= \frac{1-(-10)^n}{1-(-10)} \,.$$

Since the left side is an integer, the right side is an integer, which proves the claim. THis is overkill though....

share|improve this answer

You don't need induction, as mac points out, but if you want to complete the inductive argument you started, you could do something like this:

$10^{n+1}=10\cdot 10^n\equiv(-1)\cdot(-1)^n=(-1)^{n+1} \; (\mod 11)$

share|improve this answer

For the induction the following will be useful to show that the difference is a multiple of 11:

  1. $10^0 - (-1)^0 = 1-1 = 11 \times 0$
  2. $10^{n+1} - (-1)^{n+1} = 10\times (10^n -(-1)^n) -11 \times (-1)^n $, i.e. the difference between (by the inductive hypothesis that $10^n -(-1)^n$ is a multiple of 11*) a multiple of 11 and another multiple of 11.

An alternative method is

$$10^{n+1} - (-1)^{n+1} = 11 \times \sum_{i=0}^{n} 10^i(-1)^{n-i}$$

share|improve this answer

Direct proof: $10^n=(11-1)^n=11(\dots)+(-1)^n$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.