Solve the recurrence a_n = 2 a_{n-1} + n with a_0 = 0 in closed form, and give a_10.

Solve the recurrence a_n = 2 a_{n-1} + n with a_0 = 0 in closed form, and give a_10.

Approach: Add the general solution of the homogeneous part to a particular solution guessed as a linear polynomial in n, then fix the constant from the initial value.

2036. The homogeneous solution of a_n = 2 a_{n-1} is A * 2^n. For the forcing term n, try the particular solution a_n = b n + c, which requires b n + c = 2(b(n-1) + c) + n, so b n + c = (2b + 1) n + 2c - 2b. Matching coefficients gives b = 2b + 1, so b = -1, and c = 2c - 2b, so c = 2b = -2. The general closed form is a_n = A * 2^n - n - 2, and the initial condition a_0 = 0 forces A = 2, giving a_n = 2^{n+1} - n - 2. Checking, a_1 = 4 - 3 = 1 and a_2 = 8 - 4 = 4, which match direct iteration. At n = 10 the value is 2048 - 12 = 2036.

Follow-up: How does the closed form change when the forcing term is 2^n instead of n, and why does the guess have to be multiplied by n there?

Key concepts: homogeneous solution, particular solution, closed form, initial condition.