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:


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


leading to the general form:


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!