# Proof by induction

1. Mar 4, 2014

### mikky05v

1. The problem statement, all variables and given/known data
I have two problems that I can't figure out how to turn into summations so I can solve them.

1. Prove by induction ($\forall$n)P(n), P(n) is 3|(4$^{n}$-1)
I believe the | means divides.

2. Prove by induction ($\forall$n)P(n), P(n) is n! $\leq$n$^{n}$

2. Mar 5, 2014

### maajdl

The symbol "|" probably means "divides" in this context:

http://en.wikipedia.org/wiki/List_of_mathematical_symbols

What are the meaning of these "P(n)"?

There you can read what a proof by induction means:

http://en.wikipedia.org/wiki/Mathematical_induction

For example, for problem 1, the first step is to check the statement for some special value of n (typically a small value).
Take n = 1, for example, and check that 3 divides (4^n-1), which is quite obvious.
Then try to prove that if the statement is true for any special value n, then it must also be true for the next value n+1 .
This can be done in two lines of algebra.

Have fun.

3. Mar 5, 2014

### micromass

Staff Emeritus
Turn into summations? What do you mean with that?

4. Mar 5, 2014

### mikky05v

So that i can solve them with a classic proof by induction where you solve p (1) and show thats true then solve p (k) and p (k+1) using the induction hypothesis. I dontt know how to do this properly without a summstion or how to turn those statements into summations in the form
$$\sum_{i=1}^{n}i=n$$
does that ake sense?

5. Mar 5, 2014

### LCKurtz

No. Your problem has nothing to do with summations.

6. Mar 5, 2014

### micromass

Staff Emeritus
Perhaps the problem is that you'e only seen induction before when you had to do stuff with summations. But summations are not necessary in order for a proof by induction to work.

Let's prove (1). You need to prove $P(n)$ holds for all naturals $n$. If you prove this by induction, then you need to prove two things:

(a) Prove that $P(1)$ holds.
(b) Prove that if $P(k)$ holds for some natural $k$, then $P(k+1)$ holds.

Can you prove (a) first?

7. Mar 5, 2014

### mikky05v

Hmmm. Ok yes p (1) works, and icanpull out a p (k) and a p (k+1) but everything i know how to do stops there.

1. P (1) 3|4^1-1=3 and yes 3|3
$$p (k)= 3|(4^k-11)$$
$$p (k+1)= 3|(4^{k+1}-1)$$
now what?

Last edited: Mar 5, 2014
8. Mar 5, 2014

### mikky05v

Ok so
$$p (k)= 3|(4^k-1)$$
and i need to get to
$$p (k+1)=3|(4^{k+1}-1)$$
So p (k) is for some m
$$4^k -1=3m$$
And p (k+1) is for some p
$$4^{k+1}-1=3p$$
Now manipulating p (k) i can add 1 to bothsides and thenmultiply both sides by 4 and then subtract 1
$$4^{k+1}-1=4(3m+1)-1$$
I feel like this is a good direction but i dont know what to do to prove 3|rhs

9. Mar 5, 2014

### micromass

Staff Emeritus
Good. Now prove that $4(3m + 1) - 1$ can be written as $3a$ for some integer $a$.

10. Mar 5, 2014

### mikky05v

Alright i think i have a solution for both of them now. Thank you all very much for your help