In class, we figured out how to find the closed form of a recursive definition through the "basic 5 steps method".
Example function T(n):
If n = 1, T(1) = 1
If n > 1, T(n) = T(n-1)+1
Step 1: Iterate through a few times:
k = 1 T(n) = T(n-1)+1
k = 2 T(n) = T(n-2)+2
k = 3 T(n) = T(n-3)+3 ...etc.
Step 2: find a pattern
T(n) = T(n-k)+k
Step 3: solve for k
n - k = 1
k = n - 1
Step 4: substitute k into original... Step 5: prove via induction...
However this has me a bit confused with 2 instances of recursion in the same function:
Eg:
If n = 0, T(n) = 1
If n = 1, T(n) = 2
If n > 1, T(n) = T(n-1)+ T(n-2)
I'm not quite sure what to do for step 3 in this case as everything i've tried so far has failed for step 4.
Thanks in advance.