I'm trying to prove by way of induction that:
The base case is obviously true as
I then took the inductive step and came up with the following:
I then figured that if (assumption), then if the amount that the LFH is being multiplied by each time is > the amount that the RHS is being multiplied by each time, then the LHS must always be > RHS and the statement is true.
So if:
then the original statement is true.
Since then the LHS multiple is always > 4 which is > 2 (RHS multiple), therefore the LHS is always greater than the RHS and the statement is true.
Is this a valid proof? What are some other ways I could prove this?
Thanks.
You have the right idea, but should not have written at the start
(k+1)! > 2^(k+1)
That is what you want to PROVE, so don't state it first as if it's already been proven.
Rather, you could write it this way:
Suppose (as the inductive hypotheis) k! > 2^k.
And k+1 > 2.
So, by monotonicity, (k+1)! = (k+1)k! > 2(2^k) = 2^(k+1).
Ok, thanks. That makes sense, I guess I was just trying to show my thought process of how I got to the proof by writing it out like that.
I have another example and I didn't quite understand the steps given in the notes so I tried to apply a similar method to the new statement; I was wondering if it was also valid and if I post the notes that maybe someone could understand these notes.
Show
My proof:
Base case is true.
Induction step = assume and test whether
Similar to my other proof, given my assumption, if the change in the LFH >= the change in the RHS then the statement must be true, i.e., if
then the statement is true. Since the LHS >= 16 > 9 (RHS), the statement is true. Although I don't feel like I have PROVEN it for all changes in each side.
Notes I have on this:
Hence T(n) implies T(n+1)
I didn't understand the step to n^2 + 4n.
Sorry if I made some mistakes above, posting this in between classes - rushing.
Thanks.
When you want to mention various objectives in the proof, use a word like 'show'.
For example:
Show that if k>=4 then k! > k^2.
By induction on k:
Base case. 4! > 4^2.
Induction hypothesis: k! > k^2.
Show that (k+1)! > 2^(k+1).
etc...
So, always make clear to the reader whether a formula is something you WANT to show as opposed to something you HAVE shown. If you mention a formula without such qualification, the reader should be allowed to take it that the formula is something that has already been proven, either previously in the subject or in your own proof.
Without induction.
_______________________
The Leverage Season 5 DVD crew helps a veteran hockey player who thinks team management!