Use induction and the recursion formula:
Let be the statement that , for all positive integer .
Base case: says that which is true.
Inductive step: Assume to be true, that is, for some positive . It remains to show that is also true, that is, .
........... What is the red equal to? Recall the recursive definition and everything should work out.