请求协助求解递推关系式T(n) = T(9n/10) + n

Great job getting started with expanding the recurrence—you’re already on the right track! Let’s finish up the solution by completing the pattern you’ve started and simplifying the geometric series at the core of the problem.

Step 1: Finalize the k-th Expansion #

You correctly expanded the recurrence k times to reach:

T(n) = T( (9^k n)/10^k ) + n * [ (9/10)^0 + (9/10)^1 + (9/10)^2 + ... + (9/10)^{k-1} ]

Since we know T(1) = 0, we need to find k such that (9^k n)/10^k = 1. Rearranging this gives:

(9/10)^k = 1/n → k = log_{10/9} n

Instead of working directly with logarithms, let’s first compute the sum of the geometric series in the equation.

Step 2: Calculate the Geometric Series Sum #

The sum inside the brackets is a finite geometric series with first term a=1, common ratio r=9/10, and k terms. The formula for this sum is:

Sum = (1 - r^k) / (1 - r)

Plugging in r=9/10:

Sum = (1 - (9/10)^k) / (1 - 9/10) = (1 - (9/10)^k) / (1/10) = 10*(1 - (9/10)^k)

Step 3: Substitute Back and Simplify #

From earlier, we know (9/10)^k = 1/n. Substitute this into the sum:

Sum = 10*(1 - 1/n)

Multiply by n (from the expanded recurrence) and use T(1) = 0:

T(n) = 0 + n * 10*(1 - 1/n) = 10n*(1 - 1/n) = 10n - 10

Quick Verification #

Let’s confirm this formula works with the base case and sample values:

• For n=1: T(1) = 10*1 -10 = 0 ✔️ (matches the given condition)
• For n=10/9: T(10/9) = T(1) + 10/9 = 10/9, and 10*(10/9) -10 = 10/9 ✔️
• For n=(10/9)^2 = 100/81: T(100/81) = T(10/9) + 100/81 = 190/81, and 10*(100/81) -10 = 190/81 ✔️

The closed-form solution is T(n) = 10n - 10.

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