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
    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.2012-08-24
  • 0
    @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$.2012-08-24
  • 0
    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 : )2012-08-24
  • 0
    @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: ...2012-08-24
  • 0
    ... $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.)2012-08-24
  • 0
    One last question $$ = 16 \times 16^{n+1} + 4 \times 4^{n} - 2 = 4 \times ( 16^{n+1} + 4^{n} -2 ) + 12 \times 16^{n+1} + 6 = $$ Expanding all of tis is still giving me trouble this is the second similar example i got lost from + 12 *. Can you show me how this was expanded. I guess 12 is the remainder if i expand everything by 4 but why * 16 then.2012-08-24
  • 0
    Think something got bugged everything is gone in to left collumn.2012-08-24
  • 0
    @kellax: 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.stackexchange.com/a/792307/242)2014-05-13