Easy proof by induction question ?

2020-06-22 7:16 pm
2^n>11n, n>=7

I’m struggling with proving the 2^k+1 stage. I don’t get how to go from 2^(k+1)>22k to its > 11(k+1)

回答 (8)

2020-06-22 11:54 pm
✔ 最佳答案
You've gotten to this point:
2^(k+1) > 22k

22k 
= 11(2k)
= 11(k + k)

Since k ≥ 7, we know k > 1.
So 11(k + k) > 11(k + 1)

We've shown:
2^(k+1) > 22k = 11(k+k) > 11(k+1)

So:
2^(k+1) > 11(k+1)
2020-06-22 10:42 pm
P(n): 2ⁿ > 11n for n ≥ 7

When n = 7:
2⁷ = 128
11×7 = 77
Hence, P(1) is true.

Assuming that P(k) is true, i.e. 2ᵏ > 11k and thus 2ᵏ - 11k > O
Prove that: P(k + 1) is true, i.e. 2ᵏ⁺¹ > 11(k + 1)

Proof:
2ᵏ⁺¹ - 11(k + 1)
= 2×2ᵏ - 11k - 11
= 2×2ᵏ - 2×11k + 2×11k - 11k - 11
= 2×(2ᵏ - 11k) + 11k - 11
= 2×(2ᵏ - 11k) + 11(k - 1) > 0
for 2×(2ᵏ - 11k) > 0 as 2ᵏ - 11k > 0
and 11(k - 1) > 0 when k ≥ 7

Hence, 2ᵏ⁺¹ - 11(k + 1) > 0
and thus P(k + 1) is true when assuming P(k) is true.

P(1) is true, and P(k + 1) is true when assuming P(k) is true.
By the principle of Mathematical Induction, 2ⁿ > 11 n for n ≥ 7
2020-06-23 12:38 am
Let P(n) be a statement such that 2^n>11n, n>=7.
P(7): 2^7-11(7)=51>0=>2^7>11(7)=>p(7) is true.
Assume P(k) is true for an integer k>=7; i.e.
2^k-11k>0. Then

2^(k+1)-11(k+1)=
2^k+2^k-11k-11=
(2^k-11k)+(2^k-11)>
(2^k-11k)+(2^7-11)=
(2^k-11k)+117>0
=>
2^(k+1)>11(k+1)
=>
P(k+1) is true.

Following the principle of math-induction,
P(k) is true for all natural numbers>=7.
2020-06-22 9:07 pm
Proof by induction is a two step process.
1) prove it for some base value (here, it would be n=7)
2) prove that if it is true for "n", then it remains true for "n+1" (or any other letter you decide to use).

1) for n=7
2^7 > 11*7
128 > 77
true

2) assume that 2^n > 11n is true.
Does it remain true for "n+1"?

2^(n+1) > 11(n+1)
becomes
2^n * 2 > 11n + 11
2^n + 2^n > 11n + 11
we know 2^n > 11n, therefore if we subtract 2^n from the left and 11n from the right, we will have subtracted much more from the left than from the right. If what remains is true, then the original (before subtraction) is true
2^n > 11
is definitely true for any n = 7 or greater than 7.
2020-06-22 7:42 pm
2^(k+1) = 2 * 2^k > 2 * [left for you]. 
2020-06-22 9:13 pm
22k = 11k + 11k
11k + 11k > 11k + 11 for k > 1
11k + 11 = 11(k+1)
2020-06-22 8:20 pm
2^7 = 128, 11(7) = 77. 2^n > 11n for n = 7;
Put f(n) = 2^n - 11n. Suppose, for some k > 7, that f(k) > 0. We would now like to
show that f(k+1) > f(k). Consider f(k+1) - f(k) = 2^(k+1) - 11(k+1) -[2^k - 11k] =
2^k(2-1) -11[(k+1)-k] = 2^k - 11, clearly > 0. We have now shown that f(k) > 0
implies that f(k+1) > 0. 
2020-06-22 7:57 pm
I don’t get how to go from 2^(k+1)>22k to its > 11(k+1)

Like this:
22k > 11(k+1), for any k > 1
End of story.


Full solution
If 2^k > 11k for some k ≥ 7,
2^(k+1) = 2 * 2^k > 2 * 11k
2^(k+1) > 22k
And by extension 2^(k+1) > 11(k+1), since we know 22k>11(k+1) for k ≥ 7

2^n>11n is true for n=7 so it is true for all n ≥ 7


收錄日期: 2021-04-18 18:34:18
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20200622111631AAKXCLo

檢視 Wayback Machine 備份