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

#### ThunderBase

##### New member
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!

#### Harry_the_cat

##### Senior Member
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
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
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
Thank you all. Makes perfect sense now!