Induction

**ff4930** · October 5th 2007, 02:14 PM

See reply below, thanks!

**Jhevon** · October 5th 2007, 02:20 PM

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$

Thats the confusion, please help.

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

**ff4930** · October 5th 2007, 02:28 PM

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

(k+1)! < (k+1)^(k+1)..thats how far I got, please help.

**Plato** · October 5th 2007, 02:48 PM

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?

**ff4930** · October 5th 2007, 02:59 PM

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.

**Plato** · October 5th 2007, 04:07 PM

It is really so simple!
$k + 1 > k\quad \Rightarrow \quad k^k < \left( {k + 1} \right)^k$

**darken4life** · October 5th 2007, 04:22 PM

wrong post sorry

Thread: Induction

LinkBack

Thread Tools

Display

Induction

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

induction help

Mathemtical Induction Proof (Stuck on induction)

Induction!

Search Tags