How do you solve a recurrence with a summation function inside: $t(n) = 1 + \sum\limits_{j=0}^{n-1} t(j)$

Show that

$$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$

is the same as

$$t(n) = 2^n$$

Initial condition $t(0) = 1$

Solution 1:

The relation between differential equations and integral equations is very similar to the relation between difference equations and summation equations. This summation equation is equivalent to the initial value problem (difference equation) $\Delta t(n)=t(n)$ with $t(0)=1$, where $\Delta t(n):=t(n+1)-t(n)$. Indeed, if you sum this equation from $0$ to $(n-1)$, what you get is $$t(n)-t(0)=\sum_{k=0}^{n-1}\Delta t(k)=\sum_{k=0}^{n-1}t(k).$$ Do this and see that you have a telescoping series, which simplifies to $t(n)-t(0)$. Now, applying the initial value, we end up with $$t(n)=1+\sum_{k=0}^{n-1}t(k).$$ Let us now, try to solve the corresponding difference equation. This is an autonomous difference equation and hence we will seek for an exponential type solution (as in the case of autonomous differential equations). Let us suppose that the solution is of the form $t(n)=\lambda^{n}$, which yields $$\lambda^{n+1}-\lambda^{n}=\lambda^{n},\quad\forall n$$ i.e., $$\lambda-1=1\implies\lambda=2.$$ Thus, the solution is of the form $t(n)=c 2^{n}$ (since the equation is linear any constant multiple of $2^{n}$ will be a solution). Using the initial value $t(0)=1$, we see that $c=1$, which shows that the solutions is $t(n)=2^{n}$.

For this theory, I can redirect you to the very nice reference [1].

References

[1] Samuel Goldberg, Introduction to Difference Equations, Dover Publications, 2010. http://www.amazon.com/Introduction-Difference-Equations-Dover-Mathematics/dp/0486650847

Solution 2:

Use induction:

Base case (n = 1): $$t_1 = 1 + \sum_{ j=0}^{n-1} t_j = 1 + t_0 = 1 + 1 = 2 = 2^1$$

Inductive step.

Assume that

$$t_k = 2^k$$

Then

\begin{align} t_{k+1} &= 1 + \sum_{ j=0}^{(k+1)-1=k} t_j \\ & = 1 + \left(\sum_{ j=0}^{k-1} t_j\right) +t_k \\ & = 1 +(t_k - 1) + t_k \end{align}

( since $$t_{k+1} = 1 + \sum_{ j=0}^{k} t_j$$

which means that $$\sum_{ j=0}^{k} t_j = t_{k+1} - 1$$

and so $$\sum_{ j=0}^{k-1} t_j = t_{k} - 1.$$ )

Hence $$t_{k+1} = 1 + t_k -1 + t_k = 2t_k = 2^{k+1}$$

(by the inductive hypothesis).

The result follows by induction.

Solution 3:

The rule to remember here is very simple: the generating function of the sum of the initial $n$ terms of a sequence is obtained by multiplying the generating function of that sequence by $1/(1-z).$

In your example we put $T(z) = \sum_{n\ge 0} t_n z^n$ and we have $$t_n = 1 + [z^{n-1}] \frac{1}{1-z} T(z)$$ where $[z^n]$ is the coefficient extraction operator for formal power series.

Multiply by $z^n$ and sum over $n\ge 1$ to obtain $$\sum_{n\ge 1} t_n z^n = \sum_{n\ge 1} z^n + \sum_{n\ge 1} z^n [z^{n-1}] \frac{1}{1-z} T(z).$$ Simplifying we obtain $$T(z) - 1 = \frac{z}{1-z} + z \sum_{n\ge 1} z^{n-1} [z^{n-1}] \frac{1}{1-z} T(z).$$ This yields $$ T(z)-1 = \frac{z}{1-z} + z \frac{1}{1-z} T(z).$$ Solve this for $T(z)$ to obtain $$ T(z) = \frac{1}{1-2z}$$ so that by the geometric series $$t_n = 2^n.$$

Multiplication by $1/(1-z)$ is a very simple yet powerful tool when working with sums in recurrence relations.