1
$\begingroup$

This question already has an answer here:

This question: Solving the recurrence T(n) = 3T(n-2) with iterative method has a pretty straightforward step-by-step for solving this particular recurrence. But, I'm having trouble understanding two things.

1) How dos OP arrive at this general form? If we know T(n)=3T(n−2) and T(n−2)=3T(n−4), then my substitution gives:

T(n)=3T*3T(n−4)

Why is it not 3T*3T, or 3T^2? Is it some specific behavior of T that determines this?

T(n)=3∗3T(n−4)

leading to the general form:

T(n)=3kT(n−2k)

2) where does the above k variable come from, exactly? I understand that you'd combine the 3s to have 3^2, but how do you replace 3^2 with 3^k?

Thanks in advance!

$\endgroup$

marked as duplicate by Yuval Filmus, Patrick87 Oct 13 '14 at 20:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.