1
$\begingroup$

In an algorithm I'm developing for one of my computer science classes, I need to find the general formula for each term of the sequence $T_n$. This sequence is defined in the following way:

Define the sequences $b_n$ and $p_n$ as:

  • $p_1 = 1$ and $b_1 = 0$
  • $p_{n+1} = 2\cdot p_n$
  • $b_{n+1} = 2\cdot b_n + p_n$

Then, we define $T_n = b_n + p_n$

It's easy to see that $p_n = 2^{n-1}$, so we get the following recursion relation for $b_n$: $$b_{n+1} = 2\cdot b_n + 2^{n-1}$$

But now I'm having some trouble finding the formula for $b_n$ because of that $2^{n-1}$ term. How can this be done? I always have some trouble finding formulas for sequences given a recurrence relation, so I would appreciate some general advice/techniques for solving this kind of problem.

$\endgroup$
0

5 Answers 5

5
$\begingroup$

One of the (probably, the) most important techniques for finding explicit formulae for sequences defined by recurrences is that of generating functions. (In this case it might be overkill but it is worth learning it at some point in my opinion.)

The idea is (1) to define the formal power series $$ B(x)=\sum_{n\geq 1} b_{n} x^{n}, \qquad\qquad \mbox{(the "generating function")} $$

(2) to translate the recurrence into some equation for $B(x)$, (3) to solve this equation for $B(x)$, and, finally, (4) to re-expand $B(x)$ to get the answer.

In this case, take the recurrence $$ b_{n+1}=2b_n+2^{n-1}, $$ multiply it by $x^{n+1}$ and sum over $n\geq 1$ to obtain a relation about the generating function $B(x)$. Proceeding separately for each term in the recurrence, we have \begin{align*} \sum_{n\geq 1}b_{n+1}x^{n+1} &= b_2x^2+b_3x^3+\cdots=B(x)-b_1x=B(x), \\ \sum_{n\geq 1}2b_{n}x^{n+1}&=2xB(x), \\ \sum_{n\geq 1}2^{n-1}x^{n+1}&=\frac{x^2}{1-2x}. \end{align*} In the first equality we used that $b_1=0$ by assumption (but the method would work for any value of $b_1$), and in the third equality a geometric series. Collecting these pieces, the recurrence for the coefficients is equivalent to the (algebraic, in this case) relation $$ B(x)=2xB(x)+\frac{x^2}{1-2x}. $$ We can solve for $B(x)$: $$ B(x)=\frac{x^2}{(1-2x)^2}. $$ The final step consists in re-expanding in Taylor series $B(x)$ to read off the coefficients. With some experience you recognize that here you need the expansion $$ \frac y{(1-y)^2}=\sum_{n\geq 1}ny^n. $$ (This is, essentially, a derivative of the geometric series $\frac 1{1-y}=\sum_{n\geq 0}y^n$.) Apply it with $y=2x$ to get $$ B(x)=\frac x2\frac {(2x)}{(1-2x)^2}=\frac x2\sum_{n\geq 1}n(2x)^n= \sum_{n\geq 1}n2^{n-1}x^{n+1}=\sum_{n\geq 1}(n-1)2^{n-2}x^{n} $$ finally yielding the desired answer $$ b_n=(n-1)2^{n-2}. $$

A good reference (but there are plenty) for this method is

Wilf: Generatingfunctionology (available at https://www2.math.upenn.edu/~wilf/DownldGF.html)

$\endgroup$
4
  • $\begingroup$ but $b_n = n2^{n-2}$ does not meet the condition $b_1 = 0$ $\endgroup$ Oct 4, 2022 at 14:27
  • $\begingroup$ I read in the question that $b_0=0$ $\endgroup$
    – Giulio R
    Oct 4, 2022 at 14:31
  • $\begingroup$ I'm so sorry. it's $b_1 = 0$. Already corrected it. $\endgroup$ Oct 4, 2022 at 14:36
  • 1
    $\begingroup$ Ok I will edit, does not make much difference in the argument though $\endgroup$
    – Giulio R
    Oct 4, 2022 at 15:01
2
$\begingroup$

Maybe you can try this $ b_{n+1}=2b_n+2^{n-1}=2(2b_{n-1}+2^{n-2})+2^{n-1}=2^2b_{n-1}+2\times2^{n-1}=2^3b_{n-2}+3\times2^{n-1}=\cdots=2^{n+1}b_0+(n+1)\times2^{n-1}$

$\endgroup$
1
$\begingroup$

As a general piece of advice, guess-and-check is often the first thing to try: compute the first half-dozen terms of $b_n$ and see if you can find a pattern. Once you have a form it's a lot easier to prove that it's correct than to find it from scratch, since you can just use induction. In this case, we see: $b_1=0$, $b_2=2b_1+2^1=2$, $b_3=2b_2+2^2 = 4+4 = 8$, $b_4=2b_3+2^3=2\cdot8+8=24$, $b_5=2b_4+2^4=48+16=64$, $b_6=2b_5+2^5=128+32=160$. So we have the sequence $\langle 0, 2, 8, 24, 64, 160, \ldots\rangle$. There are a few things that stand out here: one is that all of the values are divisible by fairly large powers of two, and another is that $b_4$ is also divisible by $3$ and $b_6$ is divisible by $5$. This might suggest pulling out $(n-1)$ as a potential divisor of $b_n$, and doing that it's easy to find Giulio's formula and then to prove it.

$\endgroup$
1
$\begingroup$

Method of varying constant parameter

General solution of homogeneous equation $b_{n+1}=b_n$ looks like $b_n=c 2^n$. Solution contains constant parameter $c$ depending on initial condition.

In order to find solution of non-homogeneous equation it may be useful to consider the same solution with $c$ depending on $n$.

Let $b_n = c_n 2^n$, then $b_{n+1}=c_{n+1} 2^{n+1}$.

$$b_{n+1}=2b_n+2^{n-1}$$ $$c_{n+1} 2^{n+1} = 2 c_n 2^{n}+2^{n-1}$$ $$c_{n+1}=c_n+\frac14$$ This equation gives arithmetic sequence: $$c_n=c_1+\frac14 (n-1)$$ $$b_1=c_1\cdot 2^1 \Rightarrow c_1=\frac{b_1}{2}$$ $$c_n=\frac{b_1}{2}+\frac14 (n-1)$$ $$b_n=c_n 2^n = b_1 2^{n-1}+(n-1)2^{n-2}$$

$\endgroup$
0
$\begingroup$

You can try to solve the general solutions of the homogeneous equation (i.e $b_{n+1}=2b_n$) and then find a particular solution of the complete equation. The final solutions will be the sum of the both the general solution of the homogeneous equation and the particular solution of the complete recurrence equation. Then you find the constant with initial condition. This is similar to solving a differential equation with a non zero RHS.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .