Recursive functions:

we need to come up with a approximation for and first we calculate and it does not work so we go stepper higher and calculate and for it is correct.
but we are not sure for what approximation exactly does this work for where i is between 1 and 2.
for now we say till we prove it later.

First step we need to prove that :

we prove this by induction: and it is obvious by Simplifying the .

Second step is to Prove :

same goes for this part of the equation.

by combining 1 and 2 steps we can prove .

Recursion Tree method:

it's a bit long so I included this link

Recusrsion

Recursive functions:

First step we need to prove that :

Second step is to Prove :

Recursion Tree method: