如何用代入法求解递推公式$T_{n} = 2T_{n-1} + 4$

Alright, let's break this down step by step—since you've already tried plugging in lower-order terms like $T_{n-1}$ and $T_{n-2}$ without spotting a clear pattern, let's formalize the substitution process to turn those expansions into a solvable formula.

First: Nail down your recurrence's exact form #

First off, you need to start with a clear statement of your recurrence relation and its initial conditions. For example, let's use a common linear non-homogeneous recurrence as a demonstration:

$T(n) = 3T(n-1) + 2$, with initial condition $T(0) = 1$

Second: Expand systematically, track every term #

You mentioned trying lower-order terms, but the key here is to write out each expansion step explicitly to spot the pattern. Let's do this for our example:

• Substitute $T(n-1) = 3T(n-2) + 2$ into the original equation:
  $T(n) = 3(3T(n-2) + 2) + 2 = 3^2T(n-2) + 3*2 + 2$
• Next, substitute $T(n-2) = 3T(n-3) + 2$:
  $T(n) = 3^2(3T(n-3) + 2) + 32 + 2 = 3^3T(n-3) + 3^22 + 3*2 + 2$
• After k expansions, we can generalize this to:
  $T(n) = 3^kT(n-k) + 2\sum_{i=0}^{k-1}3i$

Third: Use initial conditions to close the expansion #

We need to get to a term we know the value of (our initial condition). For our example, when $n-k = 0$ (so $k = n$), we can substitute $T(0) = 1$:
$T(n) = 3^nT(0) + 2\sum_{i=0}^{n-1}3i$
Now compute the sum—this is a geometric series, so $\sum_{i=0}^{n-1}3i = \frac{3^n - 1}{2}$. Plug that in:
$T(n) = 3^n1 + 2\frac{3^n - 1}{2} = 3^n + 3^n - 1 = 2*3^n - 1$

Fourth: Verify your result #

Always double-check with small values to make sure you didn't make a mistake:

• $n=1$: $T(1) = 3T(0)+2 = 31+2=5$. Using our formula: $23^1 -1=6-1=5$ ✔️
• $n=2$: $T(2)=3T(1)+2=15+2=17$. Formula gives $2*9-1=17$ ✔️

Pro tips for your specific case #

• If your recurrence is linear homogeneous (no constant or non-homogeneous term), the expansion will lead directly to an exponential form—you just need to use initial conditions to solve for coefficients.
• If non-homogeneous terms are polynomials (like $n^2$) instead of constants, the sum you'll need to compute will be a polynomial sum instead of geometric—brush up on those summation formulas if you need to!

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