Solving recurrence $T(n) = 2T(n-1) + 1$

Question

I'm trying to solve this recurrence relation:

$T(n) = 2T(n-1) + 1$, $n > 0$, $T(0) = 0$

I think I may have been able to expand it, but I'm not entirely sure if it's correct. Here's what I've done:

$T(1) = 2T(0) + 1 = 2 * 0 + 1 = 1$

$T(2) = 2T(1) + 1 = 2 * 1 + 1 = 3$

$T(3) = 2T(2) + 1 = 2 * 3 + 1 = 7$

$T(4) = 2T(3) + 1 = 2 * 7 + 1 = 15$

$T(n) = 2^n - 1$

Is this the proper way to go about solving a recurrence relation? Or am I going about it wrong.

Answer 1

Is this the proper way to go about solving a recurrence relation?

Yes, and no. Typically one might use backward iteration or characteristic equations to solve a recurrence such as this. Your method works insofar as it gives you a guess for an explicit formula, but said formula needs to be proven - your formula ultimately depends on noticing a pattern, but there is no reason to suspect a priori the pattern holds.

You can check your solution by verifying the recurrence holds. Let $T(n) = 2^n - 1$. Then

$$T(n) = 2^n - 1 = 2 \cdot 2^{n-1} - 2 + 1 = 2(2^{n-1} - 1) + 1 = 2T(n-1) + 1$$

Two other ways to solve it would be iterating backwards and to use a characteristic equation. For the first, it is exactly as it sounds:

$$\begin{align} T(n) &= 2T(n-1) + 1\\ &= 2(2T(n-2) + 1) + 1 = 4 T(n-2) + 3\\ &= 4(2T(n-3) + 1) + 3 = 8T(n-3) + 7\\ &= \cdots\\ &= 2^{k}T(n-k) + (2^{k} - 1)\\ &= \cdots\\ &= 2^{n} T(n-n) + (2^{n} - 1) = 2^n T(0) + 2^n - 1 = 2^n(0) + 2^n - 1 = 2^n -1 \end{align}$$

For a characteristic equation, we turn the recurrence into an algebraic equation, a polynomial specifically, and can use the roots of that polynomial to determine up to undeterminated coefficients the general solution to the recurrence. The initial condition gives us said coefficients, completing the solution. It's a little much to go into here since the motivation is partially motivated by how one solves ordinary linear differential equations, and for some complicated recurrences more or less necessitates the use of linear algebra.

I'm not sure where would be a good resource to learn of these, but this PowerPoint seems to get your started at least: http://nms.lu.lv/wp-content/uploads/2016/04/21-linear-recurrences.pdf.

Answer 2

More generally, if $t(n) = at(n-1)+b $ we would like to find a $c$ such that $t(n)-c = a(t(n-1)-c) $.

This is $t(n) =at(n-1)-ca+c =at(n-1)-c(a-1) $, so we want $-c(a-1)=b$ or $c = -\dfrac{b}{a-1} $.

Letting $s(n) = t(n)-c$, we have $s(n) = as(n-1) $, so, for $k \ge 1$, $s(n) =a^ks(n-k) $.

Setting $k = n$, $s(n) = a^ns(0)$ or $t(n)-c = a^n(t(0)-c) $ or $t(n) =a^nt(0)-ca^n+c =a^nt(0)-c(a^n-1) =a^nt(0)+\dfrac{b(a^n-1)}{a-1} $.

If $a=2, b=1$, this gives $t(n) =2^nt(0)+(2^n-1) $.