0
$\begingroup$

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.

  • 3
    $12^{2(n+1)-1}=12^{2n+1}=12^2\,12^{2n-1}$. In general $a^{s+t}=a^sa^t$. – 2012-08-22

2 Answers 2

1

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

  • 0
    @kella$x$: I tried to cram too much MathJax into the comment; I’ve moved it to my answer instead. – 2012-08-24
1

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

$\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\ i^{n}}{i\,(i\!+\!1)}\equiv\,\frac{i^{n+1}}{-1}$

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.\:$ Thus, 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.

  • 0
    See also [this answer.](http://math.sta$c$kex$c$hange.com/a/792307/242) – 2014-05-13