You have done the base case so I won't worry about that, so let's assumeOriginally Posted by Nichelle14
this is true for some , that is for this :
Now multiply both sides by , which would be the next term
of the product on the Left Hand Side (LHS) to give:
Now if we can prove that the RHS of is less than or equal
this will be sufficient to prove:
which is what we need for the induction step.
So we now seek to proove:
Now is true iff (if and only if):
which itself is true iff:
Which is true iff:
multiplying both sides of the above out give this is true iff:
which is true as the coefficients of the powers of on the LHS
are all the corresponding coefficients on the RHS, and so
the induction step is proven.