You have been asked to prove
Let's define the above statement as . First we shall prove that is true and that is true. We have
thus is true. Now assume that is indeed true and hence giving,
If we look at the Right hand side and take out a common factor of this leads to
Note that thus giving
Hence we have proven . We conclude that since we have proven that is true and that is true then by induction we have proven that is true and .