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.

I was kind of lost with the following example of induction: $$ (11^{n+1} + 12^{2n-1}) \mathbin{\%} 133 = 0 $$

It shows the following steps to solve it: (I excluded base proof for n = 1)

$$ 11^{(n+1)+1} + 12^{2\cdot(n+1)-1} = $$ $$ = 11 \cdot 11^{n+1} + 12^{2} \cdot 12^{2n-1} = $$ $$ = 11 \cdot 11^{n+1} + 11 \cdot 12^{2n-1} + 133 \cdot 12^{2n-1} = $$ $$ = 11 \cdot ( 11^{n+1} + 11 \cdot 12^{2n-1}) + 133 \cdot 12^{2n-1} $$ $$ = 11 \cdot 133k + 133 \cdot 12^{2n-1} = $$ $$ = 133 (11k + 12^{2n-1}) $$

I prooven for n=1, but i am totally confused by what follows next in this example there is no description in the book why are these steps taken whats going on etc.

I get the first line expanding to n+1 but i dont know how he gets $$ 12^{2} $$ from factoring that. And i dont get the rest of it.

Thanks in advance for any help.

share|improve this question
3  
$12^{2(n+1)-1}=12^{2n+1}=12^2\,12^{2n-1}$. In general $a^{s+t}=a^sa^t$. –  André Nicolas Aug 22 '12 at 19:54
    
Thank you, you rock : ) –  kellax Aug 22 '12 at 20:03
add comment

2 Answers 2

up vote 1 down vote accepted

Most of the missing manipulations are just applications of the distributive law, $a(b+c)=ab+ac$.

First,

$$\begin{align*} 12^{2(n+1)-1}&=12^{2n+2-1}=12^{(2n-1)+2}\\ &=12^{2n-1}\cdot12^2=12^2\cdot12^{2n-1}\\ &=144\cdot12^{2n-1}=(11+133)\cdot12^{2n-1}\\ &=11\cdot12^{2n-1}+133\cdot12^{2n-1}\;. \end{align*}$$

this gets you down to the line $11 \cdot 11^{n+1} + 11 \cdot 12^{2n-1} + 133 \cdot 12^{2n-1}$. Then

$$11\cdot 11^{n+1}+11\cdot12^{2n-1}=11\left(11^{n+1}+12^{2n-1}\right)\;,$$

not $11\left(11^{n+1}+11\cdot12^{2n-1}\right)$. Your induction hypothesis was that $11^{n+1}+12^{2n-1}$ is divisible by $133$, so there is some integer $k$ such that $11^{n+1}+12^{2n-1}=133k$. Thus,

$$\begin{align*} 11^{(n+1)+1}+12^{2(n+1)-1}&=11\left(11^{n+1}+12^{2n-1}\right)+133\cdot12^{2n-1}\\ &=11\cdot133k+133\cdot12^{2n-1}\\ &=133\left(11k+12^{2n-1}\right) \end{align*}$$

is also a multiple of $133$.

Added to answer question in comments:

$$\begin{align*}16\cdot16^{n+1}+4\cdot4^n-2&=(4+12)16^{n+1}+4\cdot4^n-2\\&=4\cdot16^{n+1}+12\cdot16^{n+1}+4\cdot4^n-2\\&=4\cdot16^{n+1}+4\cdot4^n+12\cdot16^{n+1}-8+6\\&=4\cdot16^{n+1}+4\cdot4^n-4\cdot2+12\cdot16^{n+1}+6\\&=4\left(16^{n+1}+4^n-2\right)+12\cdot16^{n+1}+6\end{align*}$$

share|improve this answer
    
How do you get from that last line that the statement 133(11k+12..) is also divisible by 133 for all xeR. I understand how u got to 1 line before the last one but i dont understand how the last line proves the statement. We didnt take any examples like this in class and i cant get in touch with my professor for him to explain me this in detail. –  kellax Aug 24 '12 at 15:38
    
@kellax: Let $P(n)$ be the statement that $11^{n+1}+12^{2n-1}$ is divisible by $133$. You checked that $P(1)$ is true. The calculation above shows that if $P(n)$ is true, then so is $P(n+1)$. That is, it shows that if $11^{n+1}+12^{2n-1}$ is divisible by $133$, then so is $11^{(n+1)+1}+12^{2(n+1)-1}$; that’s the last line above. Once you know that $P(1)$ is true and that $P(n)$ implies $P(n+1)$ for all $n\ge1$, the principle of mathematical induction lets you conclude that $P(n)$ is true for all $n\ge1$. –  Brian M. Scott Aug 24 '12 at 15:48
    
But why do i need to do the induction step then wouldnt prooving by just P(1) base step be enough. Also i cant thank you enoug for explaining this in very direct and understandable way. Thanks : ) –  kellax Aug 24 '12 at 16:19
    
@kellax: To see why you need the induction step, consider this silly ‘theorem’: for every positive integer $n$, $n=1$. Here $P(n)$ is the statement $n=1$. Certainly $P(1)$ is true, since $1=1$, but the ‘theorem’ is obviously false. If we could prove that $n=1$ implies that $n+1=1$, then induction would let us conclude that all positive integers are equal to $1$. Fortunately, we can’t prove that induction step. Just checking that $P(1)$ is true tells you nothing about $P(2),P(3)$, etc. But if you also know that $P(n)$ implies $P(n+1)$ for all $n\ge1$, then you can reason as follows: ... –  Brian M. Scott Aug 24 '12 at 16:28
    
... $P(1)$ is true, and $P(1)$ implies $P(2)$, so $P(2)$ is true; now $P(2)$ is true, and $P(2)$ implies $P(3)$, so $P(3)$ is true; and so on. (There are better, more rigorous ways of looking at it, but I think that this is the clearest to begin with when you’re having trouble with the idea.) –  Brian M. Scott Aug 24 '12 at 16:29
show 3 more comments

More simply: $\displaystyle\rm\: mod\ 133\!:\ 12^{2n-1}\equiv \frac{144^n}{12}\equiv \frac{11^n}{12}\equiv\frac{11^{n+1}}{11\cdot 12}\equiv\frac{11^{n+1}}{-1}\:\Rightarrow\:11^{n+1}+12^{2n-1}\equiv 0$

$\displaystyle\rm mod\ i^2\!+\!i\!+\!1\!:\, (i\!+\!1)^{2n-1}\!\equiv \frac{(i^2\!+\!2i\!+\!1)^n}{i\!+\!1}\equiv \frac{i^n}{i\!+\!1}\equiv\frac{i^{n+1}}{i\,(i\!+\!1)}\equiv\frac{i^{n+1}}{-1}\Rightarrow\, i^{n+1}\!+\!(i\!+\!1)^{2n-1}\!\equiv 0$

Remark $\ $ Note how the use of congruence arithmetic reduces the inductive step to the trivial induction $\rm\:mod\ 133\!:\ 144\equiv 11\:\Rightarrow\:144^n\equiv 11^n,\:$ or $\rm\:144/11\equiv 1\:\Rightarrow\:(144/11)^n\equiv 1^n\equiv 1.\:$ Hence, by intelligent preprocessing, we've reduced the induction to the trivial induction $\rm\,1^n \equiv 1.\:$ For analogous simplifications of inductive proofs see the more powerful method of telescopy.

share|improve this answer
    
See also this answer. –  Bill Dubuque May 13 at 3:46
add comment

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.