Take 2), for example. First I would recommend writing a table

Code:

0 | 1 | 2 | 3 | 4 |
---------------------------
c0 | c1 | c2 | c3 | c4 |

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.

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.