I have been given the following recurrence relation:

$b_{n} = (−1)^{n}(n + 1)a_{0} + (−1)^{n−1}(n)a_1 + · · · + (−1)(2)a_{n−1} + a_n $

I am trying to find a generating function for $b_{n}$ in terms of the generating function for $a_{n}$

I get the pattern for the sequence is $-1^{n}(n+1),-1^{n-1}(n), -1^{n-2}(n-1) \dots -1^{n-(n-1)}(2), -1^{n-n}(1)$

However, the thing that confuses me is how I would index this sequence. Is there a way of indexing 'backwards', such that the sum goes from n to zero. For example:

$\sum_{k=n}^{0} = ((k+1)(-1)^{k})a_k\ x^{n-k}$

However, I have no idea how I would be able to express this in closed form, let alone whether it is possible. and as such I was wondering whether someone could explain what direction I could take.

I have also thought of modifying the sequence to make it so that:

$\frac{b_{n}}{g(n)} = a_{n}$ where $g(n) = \frac{1}{1+n} + \frac{2}{1-n}$ which I believe is the closed form expression for the sequence 1,-1,1,-1,1.

However, this still leaves me with the problem of finding the sequence for $a_{n}$ which would still be $(n+1)a_{0} + (n)a_{1} + \dots + (2)a_{n-1} + (1)a_{n}$

I am confused as to whether the above sequence is finite or infinite, as such I was wondering whether someone could explain what direction I could take from here.

Thanks in advance.

  • $\begingroup$ The suggested writing $\sum_{k=n}^0$ is not helpful, since a sum is defined to be zero when the upper limit is less than the lower limit. A way to cope with it is addressed in my answer at (2). $\endgroup$ – Markus Scheuer Apr 29 '18 at 13:58

We consider a generating function $A(z)=\sum_{n=0}^\infty a_n z^n$ and are looking for a generating function $B(z)=\sum_{n=0}^\infty b_n z^n$ with \begin{align*} b_n&=(-1)^n(n+1)a_0+(-1)^{n-1}na_1+\cdots -2a_{n-1}+a_n\\ &=\sum_{k=0}^n(-1)^{n-k}(n+1-k) a_k\tag{1} \end{align*}

We apply the Cauchy product formula. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^n]A(z)=a_n \end{align*}

We obtain from (1): \begin{align*} \color{blue}{b_n} &=\sum_{k=0}^n(-1)^{n-k}(n+1-k) a_k\\ &=\sum_{k=0}^n(-1)^{k}(k+1) a_{n-k}\tag{2}\\ &=\sum_{k=0}^n\left([z^k]\frac{1}{(1+z)^2}\right)\left([z^{n-k}]A(z)\right)\tag{3}\\ &\,\,\color{blue}{=[z^n]\frac{1}{(1+z)^{2}}A(z)} \end{align*} and conclude \begin{align*} \color{blue}{B(z)=\frac{A(z)}{(1+z)^2}} \end{align*}


  • In (2) we change the order of summation by replacing the index $k$ with $n-k$.

  • In (3) we use the series representation \begin{align*} \sum_{k=0}^\infty(-1)^k(k+1)z^k=\frac{1}{(1+z)^2} \end{align*} and apply the Cauchy product formula \begin{align*} Q(z)&=\sum_{k=0}^\infty q_kz^k,\qquad R(z)=\sum_{j=0}^\infty r_jz^j\\ Q(t)R(t)&=\sum_{n=0}^\infty\left(\sum_{{k+j=n}\atop{k,j\geq 0}}q_kr_j\right)t^n=\sum_{n=0}^\infty \left(\sum_{k=0}^n q_k r_{n-k}\right)t^n\\ &=\sum_{n=0}^\infty\sum_{k=0}^n \left([z^k]Q(z)\right)\left([z^{n-k}]R(z)\right)t^n \end{align*}

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.