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)

Test 2

I was supposed to write about the test over the weekend but didn't have the chance to. Well another test down and one more to go (and by looking at the schedule....its on the very last day of school). I say this test went much better than Test 1. I didn't have any time management problems, I understood and read the questions correctly (unlike from the last test, the Fibonacci question). For the first question I got was the time complexity question. I basically knew how to do it since it was very similar to the question in the assignment. So I think by knowing that easily, it gave me more time to focus on the other two questions.

The second question was the precondition/postcondition proof and I was comfortable enough that I think i answered it correctly but something on the back of my mind says the proof isn't as "solid" as it should be. I was discussing with one of my friends about one of the cases where the the length of the string was greater than one (meaning it has to call the recursive function) where he had done sub cases for if there are no vowels found, and if the vowel was found. For me, I didn't take that approach and kind of merged the both sub cases together. I think i would have been better to do sub cases but I hope that it really only matters of how you explain yourself.

Finally, the last question was the loop invariant proof and I think this is where I will loose my marks. I think my understanding of loop invariant wasn't as clear to me as I thought after discussing with a couple of friends after the test. I think I might have to stop by Danny's office hour so I can get some help with that particular part. I really don't know how they will mark the question you don't get the initial conjecture or in this case the loop invariant since that is the main part of proving your point.

Overall, I think i did fine, its now just a matter of waiting...but at least we get our marks very quickly unlike my csc209 course (for those who are taking it this semester) that we haven't gotten our A1 mark that was due over a month ago as well our A2.