如何用递推迭代法求解递推式T(n) = 3T(n-2) + c？

Hey there! Let's walk through how to fully solve this recurrence relation using the iteration method—perfect for extending whatever partial work you've already completed. I'll break it down into clear, actionable steps.

Step 1: Iteratively Expand the Recurrence #

First, let's start expanding the recurrence relation to spot a pattern:

• 1st iteration: T(n) = 3T(n-2) + c
• 2nd iteration: Substitute T(n-2) = 3T(n-4) + c into the above:

  T(n) = 3[3T(n-4) + c] + c = 3²T(n-4) + 3c + c
  

• 3rd iteration: Substitute T(n-4) = 3T(n-6) + c:

  T(n) = 3³T(n-6) + 3²c + 3c + c
  

• k-th iteration: After k expansions, we get the general form:

  T(n) = 3ᵏT(n-2k) + c(3⁰ + 3¹ + 3² + ... + 3ᵏ⁻¹)
  

Step 2: Define Boundary Conditions & Terminate the Iteration #

Recurrence relations need base cases to terminate—let's assume your problem uses standard base cases (swap these out if your problem has different ones):

• T(0) = a (where a is a constant)
• T(1) = b (where b is a constant)

We stop iterating when n-2k equals either 0 or 1, depending on whether n is even or odd.

Case 1: n is Even (n = 2m) #

If n is even, set k = m so n-2k = 0. Substitute into the k-th iteration formula:

T(2m) = 3ᵐT(0) + c(3⁰ + 3¹ + ... + 3ᵐ⁻¹)

The sum inside is a geometric series. The sum of 3⁰ to 3ᵐ⁻¹ is (3ᵐ - 1)/(3 - 1) = (3ᵐ - 1)/2. Plug this in:

T(2m) = a·3ᵐ + c·(3ᵐ - 1)/2

Replace m with n/2 to get the formula in terms of n:

T(n) = a·3^(n/2) + (c/2)(3^(n/2) - 1) = (a + c/2)·3^(n/2) - c/2

Case 2: n is Odd (n = 2m + 1) #

If n is odd, set k = m so n-2k = 1. Substitute into the k-th iteration formula:

T(2m+1) = 3ᵐT(1) + c(3⁰ + 3¹ + ... + 3ᵐ⁻¹)

Again use the geometric series sum:

T(2m+1) = b·3ᵐ + c·(3ᵐ - 1)/2

Replace m with (n-1)/2 to get the formula in terms of n:

T(n) = b·3^((n-1)/2) + (c/2)(3^((n-1)/2) - 1) = (b + c/2)·3^((n-1)/2) - c/2

Step 3: Simplify (Optional) #

If you want to write this more concisely, you can use floor/ceiling functions, but splitting into even/odd cases is usually clearer for this recurrence. For example, if your base cases are T(0) = 0 and T(1) = 0, the formulas simplify to:

• Even n: T(n) = (c/2)(3^(n/2) - 1)
• Odd n: T(n) = (c/2)(3^((n-1)/2) - 1)

Hopefully this completes your solution! If your base cases differ from the a and b I used, just swap them in and you'll get the correct result for your specific problem.

内容的提问来源于stack exchange，提问作者Fatmah