求解递推关系式Aₙ₊₁=3Aₙ+2ⁿ（A₀=1）的显式公式

Hey there! Let's work through this recurrence relation to get that explicit formula you're after. You've already done the hard part by expanding the terms and spotting the pattern—let's formalize this step by step.

First, let's restate the problem clearly to avoid confusion:

• Base case: (A_0 = 1)
• Recurrence relation: (A_{n+1} = 3A_n + 2^n) for (n \geq 0)

Step 1: Solve the homogeneous part of the recurrence #

The homogeneous version (ignoring the (2^n) non-homogeneous term) is:
(A_{n+1}^h = 3A_n^h)

This is a simple geometric sequence. Its general solution is:
(A_n^h = C \cdot 3^n)
where (C) is a constant we'll pin down later using the base case.

Step 2: Find a particular solution for the non-homogeneous term #

The non-homogeneous term here is (2^n). Since (2) isn't equal to (3) (the base of our homogeneous solution), we can assume a particular solution of the form:
(A_n^p = D \cdot 2^n)
where (D) is another constant to solve for.

Substitute this into the original recurrence:
(D \cdot 2^{n+1} = 3(D \cdot 2^n) + 2^n)

Simplify both sides:

• Left side: (2D \cdot 2^n)
• Right side: (3D \cdot 2^n + 1 \cdot 2^n = (3D + 1) \cdot 2^n)

Divide both sides by (2^n) (since (2^n) is never zero):
(2D = 3D + 1)

Solving for (D) gives us (D = -1), so our particular solution is:
(A_n^p = -2^n)

Step 3: Combine homogeneous and particular solutions #

The general solution to the non-homogeneous recurrence is the sum of the two solutions we found:
(A_n = A_n^h + A_n^p = C \cdot 3^n - 2^n)

Step 4: Use the base case to find (C) #

We know (A_0 = 1). Plug (n=0) into the general solution:
(1 = C \cdot 3^0 - 2^0)
(1 = C - 1)
(C = 2)

Final Explicit Formula #

Substitute (C=2) back in, and we get our final formula:
(A_n = 2 \cdot 3^n - 2^n)

Verify with your expanded terms #

Let's check against the examples you provided to confirm it works (note: it looks like your index is shifted by 1 compared to our definition, which is common in nested expression notation):

• Your (A_2 = 3 + 1 = 4): This matches our (A_1 = 2 \cdot 3^1 - 2^1 = 6 - 2 = 4)
• Your (A_3 = 3^2 + 3 + 2^1 = 14): This matches our (A_2 = 2 \cdot 3^2 - 2^2 = 18 - 4 = 14) ✔️
• Your (A_4 = 3^3 + 3^2 + 3 \cdot 2 + 2^2 = 46): This matches our (A_3 = 2 \cdot 3^3 - 2^3 = 54 - 8 = 46) ✔️

Everything lines up perfectly—this formula is solid!

内容的提问来源于stack exchange，提问作者D.R.