1

From a recent solution I posted here, working from an alternative path would have led to the following recurrence relation which involves a summation term:

$$T_n=\sum_{r=0}^{n-1}T_r+2^n; \qquad T_0=1\qquad (n>1)$$ How can this be solved?

Edit 3 (replaces previous edits) Initial condition is $T_0=1$. For the problem as stated, $T_1=3$ (not $4$) and does not need to be specified as an initial condition. This is actually different from the previous problem, which would have resulted in $T_n=\sum_{r=0}^{n-1}+2^{n+1}-1$.

For clarification

For the previous problem that I referred to here, the recurrence relatioships, the first two terms, and the closed form solution are as follows: $$T_n=2T_{n-1}+\color{blue}{2^n}\\ T_n=\sum_{r=0}^{n-1}T_r+\color{blue}{2^{n+1}-1}\\ T_0=1, T_1=\color{blue}4\\ T_n=(\color{blue}n+1)2^n$$

For the present problem as posted here, the recurrence relatioships, the first two terms, and the closed form solution are as follows: $$T_n=2T_{n-1}+\color{red}{2^{n-1}}\\ T_n=\sum_{r=0}^{n-1}T_r+\color{red}{2^n}\\ T_0=1, T_1=\color{red}3\\ T_n=(\color{red}{\frac n2}+1)2^n$$

Community
  • 1
Hypergeometricx
  • 22,657
  • The value of $T_0$ is actually moot to the recurrence; since as many people have noted this is essentially a degree-1 recurrence in disguise, it only needs one value for 'initialization'. $T_1$ should conceptually be derivable from $T_0$ and the value given by your formula doesn't fit the value you specify. Given this 'break' in the pattern I'd sooner write it as $T_1=4, T_n=\sum_{i=1}^{n-1}T_i+(2^n+1)$ for consistency. – Steven Stadnicki Oct 24 '15 at 16:08
  • @StevenStadnicki - Thanks for your comment. My edit must have crossed with your comment but nevertheless addresses it (hopefully!). – Hypergeometricx Oct 24 '15 at 16:14

3 Answers3

2

Put $S_n=\sum_1^n T_r$. Then $T_n=S_n-S_{n-1}=S_{n-1}+2^n$. A particular solution of the recurrence for $S_n$ is $n2^n$. The general solution is $S_n=n2^n+a2^n$, $a $ a constant.It is easy to finish.

Kelenner
  • 18,734
  • 26
  • 36
  • Yes, that was actually where it started from, but how do you conclude that a particular solution is $n2^n$, and also what the general solution is? – Hypergeometricx Oct 24 '15 at 14:57
  • The recurrence is $S_n-2S_{n-1}=2^n$. The recurrence $S_n-2S_{n-1}=0$ has for solution $2^n$ So We can seek a particular solution of the form $(an+b)2^n$. Now the general solution is a sum of the particular solution and the general solution of $S_n-2S_{n-1}=0$. – Kelenner Oct 24 '15 at 15:00
  • Did you miss out a word in "The recurrence $S_n-2S_{n-1}=0$ has for solution 2^n..."? – Hypergeometricx Oct 24 '15 at 15:03
  • "for particular solution the RHS 2^n$" is perhaps better. Sorry, I must go... – Kelenner Oct 24 '15 at 15:05
  • Thanks for your contribution (+1). Please elaborate further when you have time. – Hypergeometricx Oct 24 '15 at 16:13
2

We have $$T_{n+1}-T_{n}=\left(\sum_{r=0}^{n}T_r+2^{n+1}\right)-\left(\sum_{r=0}^{n-1}T_r+2^n\right)=T_n+2^{n+1}-2^n,$$ i.e. $$T_{n+1}=2T_n+2^n$$ for $n\ge 2$. Dividing the both sides by $2^{n+1}$ gives $$\frac{T_{n+1}}{2^{n+1}}=\frac{T_n}{2^n}+\frac 12,$$ i.e. $$U_{n+1}=U_n+\frac 12\quad\quad (n\ge 2)$$ where $U_n=\frac{T_n}{2^n}$ which should be easy to deal with.

mathlove
  • 139,939
  • Interesting approach and insightful substitution of $U_n$. Telescoping $U_n-U_{n-1}=\frac 12$ down to $U_1-U_0=\frac 12$ gives $U_n-U_0=\frac {T_n}{2^n}-\frac {T_0}{2^0}=\frac n2$ leading to $T_n=(\frac n2+1)2^n$, whereas the answer is $T_n=(n+1)2^n$. How can we reconcile this? – Hypergeometricx Oct 24 '15 at 15:10
  • 1
    @hypergeometric: After changing to $r=0$, I got $T_n=2^{n-2}(2n+5)$ for $n\ge 2$. By the way, $T_2=9$, isn't it? Then, $T_n=(n+1)2^n$ gives $T_2=12$, I think. – mathlove Oct 24 '15 at 15:37
  • @hypergeometric: $U_{n+1}-U_n=\frac 12$ holds only for $n\ge 2$. Sorry, I should have written this. – mathlove Oct 24 '15 at 15:59
  • 1
    Actually you're right. The recurrence is slightly different from the one in the previous question, and so is the value of $T_1$. This has been corrected. +1 for your contribution, the most valuable of which was the insightful division by $2^{n+1}$ and substitution of $U_n$. Your solution is accepted! – Hypergeometricx Oct 24 '15 at 16:13
1

Use generating functions. Define $T(z) = \sum_{n \ge 0} T_n z^n$, adjust indices in the recurrence:

$\begin{align} T_{n + 1} = \sum_{0 \le r \le n} T_r + 2 \cdot 2^r \end{align}$

Multiply by $z^n$ and sum over $n \ge 0$, recognize some sums in the result:

$\begin{align} \frac{T(z) - T_0}{z} = \frac{T(z)}{1 - z} + \frac{2}{1 - 2 z} \end{align}$

Plug in $T_0 = 1$, solve for $T(z)$ as partial fractions:

$\begin{align} T(z) &= \frac{1 - z}{1 - 4 z + 4 z^2} \\ &= \frac{1 - z}{(1 - 2 z)^2} \\ &= \frac{1}{2 (1 - 2 z)^2} + \frac{1}{2 (1 - 2 z)} \end{align}$

Using the binomial theorem and a geometric series:

$\begin{align} T_n &= \frac{1}{2} \cdot (-1)^n \binom{-2}{n} \cdot 2^n + \frac{1}{2} \cdot 2^n \\ &= \frac{1}{2} \binom{n + 2 - 1}{2 - 1} \cdot 2^n + \frac{1}{2} \cdot 2^n \\ &= (n + 2) \cdot 2^{n - 1} \end{align}$

vonbrand
  • 27,812