Proof by Induction Homework: Solve P(n)

[mikky05v]

Homework Statement

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

 

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

 

[micromass]

Homework Statement

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

Turn into summations? What do you mean with that?

 

[mikky05v]

So that i can solve them with a classic proof by induction where you solve p (1) and show that's 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?

 

[LCKurtz]

So that i can solve them with a classic proof by induction where you solve p (1) and show that's 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 make sense?

No. Your problem has nothing to do with summations.

 

[micromass]

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?

 

[mikky05v]

Perhaps the problem is that you'e only seen induction bllefore 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?

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?

 

[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 don't know what to do to prove 3|rhs

 

[micromass]

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
$$4^k -1=3m$$
for some m
Now 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 don't know what to do to prove 3|rhs

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

 

[mikky05v]

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