I'm new here and I could use some help on a homework question.
Given the following recursive definition:
I have to proof, using induction, that
My current proof is as follows:
The formula is correct for the cases n=0 and n=1 (Can be easily verified).
Assume the formula is correct for n, we can fill this in:
However, I think I am missing some important induction steps. I don't see the connection between the base step and the induction step.
Any help is appreciated, thanks in advance!