3

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.

tacotaco123
  • 33
  • 2
    This is a perfectly sensible way to guess the solution to a recurrence relation. One way to verify this solution is by induction: Show that it's true for $n=0$, and show that $T(n)=2^n-1\implies T(n+1)=2^{n+1}-1$. – Semiclassical Sep 09 '19 at 01:57
  • You may add to your computations, the expression for $T(n+1)$ obtained using the expression you got for $T(n)$. – Ertxiem - reinstate Monica Sep 09 '19 at 01:58
  • 1
    I'll do this instead. $$\begin{align}T(n) = 2T(n-1)+1 & \iff T(n)+1 = 2(T(n-1)+1)\ & \implies T(n)+1 = 2^n(T(0)+1) = 2^n\end{align}$$ – achille hui Sep 09 '19 at 02:34

2 Answers2

0

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.

PrincessEev
  • 43,815
  • 2
    Yet another way is to take first differences: Let $T'(n):=T(n+1)-T(n)$. Then $$T'(n)=T(n+1)-T(n)=2T(n)+1-2T(n-1)-1=2T'(n-1).$$ Then the backwards iteration immediately gives $$T'(n)=2^n T'(0)=2^n(T(1)-T(0))=2^n.$$ One completes the solution by writing \begin{align}T(n) &=T(n-1)+T'(n-1)\ &=T(n-2)+T'(n-2)+T'(n-1)\ &\vdots& \ &=T(0)+T'(1) +\cdots +T'(n-2)+T(n-1)\ &=0+1+2^2+\cdots +2^{n-1}\ &=2^n-1. \end{align} – Semiclassical Sep 09 '19 at 02:39
0

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) $.

marty cohen
  • 107,799