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.
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?
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).
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.
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.
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).
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.