Induction Question help please. (1 Viewer)

john1464 · Mar 15, 2015

3^n >2^n+n n>1

(The ">" is an equal or greater than)

Ekman · Mar 15, 2015

Hey well im going to skip the first step which is to test n=1 or n=2 and go straight into step 2.

$$ Assume $ n=k $ works for $ 3^n \geq 2^n + n $ for $ k\geq1$

$\therefore 3^k - 2^k -k \geq 0$

$$ Test $ n=k+1$

$\therefore 3\times3^k -2\times2^k-k-1\geq0$

$3\times3^k - 3\times2^k -3k + 2^k +2k -1 \geq0$

$3(3^k-2^k-k) + 2^k +2k-1 \geq 0$

$$ Since $ (3^k-2^k-k)\geq0 $ and $ 2^k +2k-1\geq 0 \therefore 3(3^k-2^k-k) + 2^k +2k-1 \geq 0$

$$ Therefore for $ n\geq1 $ works for: $ 3^n\geq2^n+n$

john1464 · Mar 15, 2015

sorry I dont see how you got the 5th line. Can you explain please?

Ekman · Mar 15, 2015

john1464 said:
sorry I dont see how you got the 5th line. Can you explain please?

I manipulated the equation by adding and subtracting stuff. For example, I had -2^k from the equation in line 4 so I could get -3*2^k. And so when you minus something , you have to add it in order to maintain the equality. Thus I subtracted -2^k and added 2^k in order to maintain the still same original equality.

john1464 · Mar 15, 2015

It wierd though my book does it so differently its really confusing

Ekman · Mar 15, 2015

For inequality questions where you require to use induction, there is no form of substitution you can use since they are inequalities. You can only show that a certain inequality exists for when you prove n=k+1. Well that's the way I was taught at least...

dan964 · Mar 16, 2015

john1464 said:
3^n >2^n+n n>1

(The ">" is an equal or greater than)

braintic · Mar 16, 2015

Ekman said:
Hey well im going to skip the first step which is to test n=1 or n=2 and go straight into step 2.

$$ Assume $ n=k $ works for $ 3^n \geq 2^n + n $ for $ k\geq1$

$\therefore 3^k - 2^k -k \geq 0$

$$ Test $ n=k+1$

$\therefore 3\times3^k -2\times2^k-k-1\geq0$

$3\times3^k - 3\times2^k -3k + 2^k +2k -1 \geq0$

$3(3^k-2^k-k) + 2^k +2k-1 \geq 0$

$$ Since $ (3^k-2^k-k)\geq0 $ and $ 2^k +2k-1\geq 0 \therefore 3(3^k-2^k-k) + 2^k +2k-1 \geq 0$

$$ Therefore for $ n\geq1 $ works for: $ 3^n\geq2^n+n$

I would be penalising you for the logic of your inductive step.
You should be starting with a-b (without the >0), then manipulating it until you have a >0 on the other side.

Your working is similar to being asked to prove a trig identity, starting with the identity you have to prove, and ending up with something like 1=1.

InteGrand · Mar 16, 2015

braintic said:
I would be penalising you for the logic of your inductive step.
You should be starting with a-b (without the >0), then manipulating it until you have a >0 on the other side.

Your working is similar to being asked to prove a trig identity, starting with the identity you have to prove, and ending up with something like 1=1.

Isn't he using 'if and only if' steps though to go from each line to the next, so his proof is valid?

Induction Question help please. (1 Viewer)

john1464

Member

Ekman

Well-Known Member

john1464

Member

Ekman

Well-Known Member

john1464

Member

Ekman

Well-Known Member

dan964

what

braintic

Well-Known Member

InteGrand

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)