Proof by Induction: ∀n ≥ 5, 2^n + 2n < n!

ThunderBase

New member
Joined
Apr 6, 2019
Messages
5
Hi All,

I'm having trouble understanding how to solve this question. I don't understand how they got those steps that I highlighted below.
Any help is appreciated.

Thanks!

discretequestion.PNG
 

Harry_the_cat

Senior Member
Joined
Mar 16, 2016
Messages
1,490
To get to the first yellow line, they have made use of the assumed statement 2^k + 2k < k!.

Do you agree that: If a<b then 2a+2 < 2b+2 ?

That's pretty much what they've done if you replace "a" with 2^k+2k and "b" with k!.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,692
The second highlighted line makes sense only when you think of the goal, which is how you have to do induction proofs. It's not something you'd think of going sequentially through the process, but a leap to the goal.

We have 2*k! + 2, and want to get to (k+1)! (that is, the former has to be less than the latter). How can we link them? Well, expressing the latter in terms of k!, it is (k + 1)k!, so that's the expression we need at this point; we just have to justify the claim that 2*k! + 2 < (k + 1)k!.

So the hard part is actually the "reason" part (and filling the gap as we read, to see that that is actually true). Can you see why k >= 5 implies 2*k! + 2 < (k + 1)k! ? Give it a try. (I personally wish they had written at least one more step in there.)
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,832
Hi All,

I'm having trouble understanding how to solve this question. I don't understand how they got those steps that I highlighted below.
Any help is appreciated.

Thanks!

View attachment 11922
Like others, I find this proof excessively concise.

We know that the proposition to be proved is TRUE for AT LEAST one integer greater than or equal to 5, namely 5 itself. Therefore it is perfectly reasonable to say

\(\displaystyle \text {Let } k \text { be ANY integer } \ge 5 \text { such that } 2^k + 2 < k!.\)

WE KNOW that there is such an integer. Now we want to show that the proposition is true for k + 1, and obviously

\(\displaystyle 2^{(k+1)} + 2(k + 1) = 2^k * 2^1 + 2k + 2 = 2 * 2^k + 2k + 2.\)

\(\displaystyle \therefore 2^{(k+1)} + 2(k + 1) = (2 * 2^k + 2k + 2) < (2 * 2^k + 2k + 2) + 2k \ \because \ 5 \le k.\)

\(\displaystyle \therefore 2^{(k+1)} + 2(k + 1) < 2 * 2^k + 4k + 4k + 2 = 2(2^k + 2k) + 2.\)

\(\displaystyle \text {But } 2^k + 2 < k! \text { by first line's definition of } k.\)

\(\displaystyle \therefore 2^{(k+1)} + 2(k + 1) < 2k! + 2.\)

\(\displaystyle \text {And } k! > k > 2 \ \because k \ge 5 \text { by definition.}\)

\(\displaystyle 2^{(k+1)} + 2(k + 1) < 2k! + 2 < k * k! + k!.\)

\(\displaystyle \text {THUS, } 2^{(k+1)} + 2(k + 1) < 2k! + 2 < k * k! + k! = k!(k + 1) = (k + 1)! \text { Q.E.D.}\)
 

ThunderBase

New member
Joined
Apr 6, 2019
Messages
5
Thank you all. Makes perfect sense now! :)
 
Top