1. ## Proof by Induction

In my book there is a following example:

Prove by induction that 3 is a factor of $4^n-1$

the example has one step which baffles(in addition to the fact that I´m already baffled by induction as it is)
$
4^{k+1} -1=4(4^k)-1$

$= 4(4^k-1+1)-1$ (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
$=4(4^k-1)+4(1)-1$ (what happens here?)

I´m a bit worried about this induction thing, because I´ve been trying to solve the homework problems for three days with very little progress. If anyone could help me with this problem I would be really grateful.

One more thing, does anyone know any good book which would have mathematical induction for dummies?

All help is appreciated very much.

2. Hello !
Originally Posted by Coach
In my book there is a following example:

Prove by induction that 3 is a factor of $4^n-1$

the example has one step which baffles(in addition to the fact that I´m already baffled by induction as it is)
$
4^{k+1} -1=4(4^k)-1$

$= 4(4^k-1+1)-1$ (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
$=4(4^k-1)+4(1)-1$ (what happens here?)
Don't forget the first case, that is for $n=1$

Now, the step. You gotta write the inductive hypothesis, in order to have it in mind. Because there's a probability of 99.9% that you'll use it.

We want to prove that if $4^k-1$ is a multiple of 3, then $4^{k+1}-1$ is one too.

So we start from $4^{k+1}-1$
As it is written, it's equal to $4(4^k)-1$

Now, you know that $4^k \quad \textbf{-1}$ is a multiple of 3. It's time to use it here. So let's write $4^k=4^k \quad \underbrace{\textbf{-1}+1}_{=0}$
By expanding, we get : $4(4^k-1)+4(1)-1=4(4^k-1)+3$

3 is obviously a multiple of 3 and $4^k-1$ is a multiple of 3, according to the inductive hypothesis. The induction is proved.

Another way of doing it is to assume that $4^k-1=3k$, k an integer. And thus $4^k=3k+1$

Then $4^{k+1}-1=4(4^k)-1=4(3k+1)-1=4*3k+4-1=3(4k+1) \quad \blacksquare$

3. $4^{k + 1} - 1 = 4^{k + 1} - 4 + 4 - 1 = 4\left( {4^k - 1} \right) + 3
$

4. Originally Posted by Coach
$= 4(4^k-1+1)-1$ (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
Pretty much. You want to somehow use the fact that $4^{k} - 1$ is a multiple of 3. By looking at $4(4^{k}) - 1$, we have the $4^{k}$ but what about the $-1$? So subtracting and adding 1 will take care of that and it just so happens that the rest of the expression turns out to be a multiple of 3.

Don't worry about not being able to get these induction proofs. Some of them do require creativity but if you just go through as many examples as possible, you will catch on to a couple of tricks such as 'adding 0' as we did above and will hopefully be able to apply them when the exam comes around.

5. Thank you so much everyone!