Problem Solving Episode- Inequalities

I guess I might as well do my first problem solving episode using the approach done by Polya.
I will show a way how to prove inequalities. For example, The proof will be very similar to proving for all natural numbers n, 2^n > 10n, but I will show how to prove k^n > 10n.

Question: Prove for all natural numbers n, there exist a natural number k, k^n > 10n

First: Understand the problem.

First we want to find a claim that suits the proof. So lets use predicate P(n), with parameter n. Claim: P(n): Prove for all natural numbers n, (*) there exist a natural number k, k^n > 10n. Now as you can see there is the unknown k. You get to choose a k. Now the claim should seem straight forward that you want to show that given any value of n, k^n will always be greater than 10n.

Second: Devise a Plan

As you notice, there is a missing part of the claim by (*). We must find a breakpoint that that it will satisfy the inequality for all natural numbers (we want in the form of n>=B, where B is the breakpoint). Here is where it gets slightly “messy”.

(1) By messiness, we will need to do a bit a scratch work in order to get a value for the breakpoint that satisfies the inequality.

(2) First look at the set of natural numbers (the set [0, inf]). Take the very base case which is n=0. As you can see k^0 = 1 is greater than 10(0) = 0. But don’t get ahead of yourself.

(3) Here is where the tricky part comes along. As we can see (2) does satisfy the proof (since 1 > 0) but don't assume that the breakpoint can be n>=0. Take a look at values n=1. Then we have k^1 > 10(1) but if we choose k to be 10 or less, this statement will fail.

(4) When you find two consecutive numbers that satisfy the inequality, then this is where we can call it our breakpoint.

For example- let k=2. If we have n=5 then 2^5 = 32 is not greater than 10(5) =50. Then when n=6, 2^6 = 64 is greater than 10(6) = 60. Check the next number for n=7 and we can see that 2^7 = 128 is greater than 10(7). Now we don't have to check anymore. The reason is because if you look at the types of functions that 10n and 2^n creates, 10n is a linear function and will always increase at a constant rate of 10 whereas 2^n is a curve and will increase more rapidly at the breakpoint. So our breakpoint would be n>=6 in this example.
Use this idea to find our breakpoint. So we can now say P(n): Prove for all natural numbers n, there exist B n >= B, there exist a natural number k, k^n > 10n where b is the breakpoint.

(5) Figure out if what type of induction you want to use. For simple inequalities like this one, simple induction seems to be the best way.

Third: Carrying out the plan

Finally we can start with our proof!

(1) As always for simple induction, it follows the usual proof structure of Base Case and Inductive Step.

(i) Base Case - find the base value n that satisfies the inequality. In the example above, your base case, n would be 6 (the breakpoint). Then P(6) is true.

(ii) Inductive Step- This is the “meat” of the code. Again following the same structure, we assume n is a natural number for n>=B, P(n). This is our Induction Hypothesis so we are assuming that k^n > 10n

Then we want to show P(n) implies P(n+1). So start with one side of the inequality. To be consistent, lets start with the left side.

So we get k^(n+1). Now when doing this, we have to break up the k^(n+1) so it we will be able to see k^n which is where we can apply the Induction Hypothesis.

Note:

(1) If k=2, then 2^(n+1) = 2^n + 2^n

(2) If k=3, then 3^(n+1) = 3^n + 3^n + 3^n

(3) In general, if k={k_1, k_2, …, k_k} where each value in the set is equal to k and there are k numbers of the values. Then k^(n+1) = k_1^n + k_2^n + … + k_k^n

So k^(n+1) = (k_1)^n + (k_2)^n + … + (k_k)^n

Now we can use our Induction hypothesis of the fact that k^n > 10n. Then

(k_1)^n + (k_2)^n + … + (k_k)^n

> 10n + 10n + … + 10n

> 10n + 10n

= 10(n+1)

We’re done! We’ve show that k^(n+1) > 10(n+1). So now we can say that P(n+1) is true and P(n) implies P(n+1)

Fourth: Wrapping up

Since P(n) implies P(n+1) relates only to the inductive step, we must conclude our statement in a general statement. So conclude that for all natural numbers n, there is exist B, n>=B, P(n)