Take 2), for example. First I would recommend writing a table
with several initial values of . Does it fit the general formula? Can you see why, or is it a total surprise? I mean that in order to prove something one has to become comfortable with the concepts of that particular problem and have some intuition why the claim should be true.
0 | 1 | 2 | 3 | 4 |
c0 | c1 | c2 | c3 | c4 |
If you did this, you already finished the base case. Now let be the statement that . The induction hypothesis is . What you need to prove is -- be sure to write and explicitly. If at this point you don't see how to prove from and the definition of , post here all of these things and describe your difficulty.