# Induction

• Oct 5th 2007, 03:14 PM
ff4930
Induction
• Oct 5th 2007, 03:20 PM
Jhevon
Quote:

Originally Posted by ff4930
Im confused at this problem, any help would be appreciated.

Let
$
a_{1} = a
$

$
a_{n} = 2a_{n-1} + 1
$

Prove by induction that
$
a_{n} = 2^(n) - 1
$

Can a be any integer?
if I put $a_{1} = 5$
then $a_{1} = 5 = 5$
if I let $n = 2$
then
$a_{2} = 2(5)+1 = 11 != 2^(n) - 1 = 2^2-1 = 3$

that's true, $a_1 = 5$ does not work for this. are you sure you copied the question correctly? have you left any information or conditions out? i think it works for $a_1 = 1$ though, then the proof would be easy, in fact, i think we can show that $a_1 = 1$ is the only plausible first term
• Oct 5th 2007, 03:28 PM
ff4930
This is an print out review exam problem, I just checked online and she has took this problem out. I had the older version. I guess my prof. saw the problem, sorry about that.

If you guys can help me on my second most frustrated Induction, it be great.

Use induction to prove that n! < n^n whenever n is a positive integer greater than 1.

Base case: n = 2
2! = 2 < 2^2 = 4 - checks!

Assume n! < n^n, n = k.

Prove that n! < n^n when n = k+1

• Oct 5th 2007, 03:48 PM
Plato
Say that $k > 1\quad \& \quad k! < k^k$.
Look at this.
$\left( {k + 1} \right)! = \left( {k + 1} \right)\left( {k!} \right) < \left( {k + 1} \right)\left( {k^k } \right) < \left( {k + 1} \right)\left( {\left[ {k + 1} \right]^k } \right)$.

Can you finish?
• Oct 5th 2007, 03:59 PM
ff4930
Quote:

Originally Posted by Plato
Say that $k > 1\quad \& \quad k! < k^k$.
Look at this.
$\left( {k + 1} \right)! = \left( {k + 1} \right)\left( {k!} \right) < \left( {k + 1} \right)\left( {k^k } \right) < \left( {k + 1} \right)\left( {\left[ {k + 1} \right]^k } \right)$.

Can you finish?

I'm sorry I'm just so bad in Induction. I can keep staring and I still wont see it.

Did you add (k+1) to both sides?
I lost you when you got up to $\left( {k + 1} \right)\left( {\left[ {k + 1} \right]^k } \right)$
Could you explain on how you got that please.
• Oct 5th 2007, 05:07 PM
Plato
It is really so simple!
$k + 1 > k\quad \Rightarrow \quad k^k < \left( {k + 1} \right)^k$
• Oct 5th 2007, 05:22 PM
darken4life
wrong post sorry