# Proof by induction for Division

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.

-
$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 : ) –  Sterling Duchess Aug 22 '12 at 20:03

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

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

-
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. –  Sterling Duchess 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 : ) –  Sterling Duchess 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

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.

-