# Solving $a_{n+1} = c_n a_n$ using generating functions

I need to solve a recurrence relation of the form for $a_n$:

$$a_{n+1} = c_n a_n,\quad n\ge 0$$

where the constants $c_n$ and the initial condition $a_0$ are given. However I do not know the $c_n$ a priori, so I would like to write down a solution for $a_n$, in some form, that shows the dependence on $c_n$. I tried the generating function approach, but the only way I see here is to define two generating functions:

$$A(x) = \sum_{n\ge0}a_n x^n,\quad B(x) = \sum_{n\ge0}c_n a_n x^n$$

Then we have:

$$\frac{A(x) - a_0}{x} = B(x)$$

This does not get me very far, because I have two generating functions and only one equation. Is there a way to tackle this problem?

• "I would like to write down a solution"... a solution of what? – 5xum Jul 31 '17 at 13:42
• Q1: What are the condition imposed on $c_n$? – thetha Jul 31 '17 at 13:44
• $c_n$ is a constant? – Dr. Sonnhard Graubner Jul 31 '17 at 13:47
• Is this any harder than $a_{n+1} = c_na_n = c_nc_{n-1}a_{n-1} = \cdots = (c_nc_{n-1}\cdots c_1c_0)a_0$? – Neal Jul 31 '17 at 14:06
• @Neal To be honest, I was trying to find a minimal example of a more complicated problem I am trying to solve, without getting into too much detail. But I see I have oversimplified. I'll try my luck in another question. Thanks! – becko Jul 31 '17 at 14:46

## 2 Answers

You have $$a_{n+1}=c_{n}a_{n}$$ Devide by $\prod_{k=0}^{n}c_{k}$ to give $$\frac{a_{n+1}}{\prod_{k=0}^{n}c_{k}}=\frac{a_{n}}{\prod_{k=0}^{n-1}c_{k}}$$ Let $$\frac{a_{n}}{\prod_{k=0}^{n-1}c_{k}}=A_{n}$$ Then $$A_{n+1}=A_{n}$$ Hence $A_{n}=A$, where $A$ is constant $$A=\frac{a_{n}}{\prod_{k=0}^{n-1}c_{k}}$$ So $$a_{n}=A\prod_{k=0}^{n-1}c_{k}$$

• why did you switch a and c? just for fun or there is a reason? – thetha Jul 31 '17 at 13:50
• Sorry, I'll correct it. I've just misread the thing) – Kiryl Pesotski Jul 31 '17 at 13:52
• Wow, very nice! Damn, you didn't need generating functions. – becko Jul 31 '17 at 13:59
• Its exponential growth right? – thetha Jul 31 '17 at 14:09
• Yes you right down $a_{n+1}=c_{n}a_{n}=(1+hb_{n})a_{n}$ and take the limit $h\rightarrow0$ to get the exponential of integral (i.e. it will be the solution of the first order ode). Moreover, if you add the inhomogeneous term, by the very same method the recurrence is solvable, and you will have the inhomogeneous term in the solution which will become an integrating factor sort of thing in the continuous limit – Kiryl Pesotski Jul 31 '17 at 14:24

Since \begin{align*} a_{n+1}&=c_na_n\\ a_n&=c_{n-1}a_{n-1}\\ &\ \ \,\vdots\\ a_1&=c_0a_0 \end{align*}

multiplication of LHS and RHS gives \begin{align*} \prod_{k=1}^{n+1}a_k&=\left(\prod_{k=0}^n c_k\right)\left(\prod_{k=0}^na_k\right) \end{align*}

Given that $a_n\ne 0$ for $n\geq 0$ we can divide by $\prod_{k=1}^na_k$ and obtain \begin{align*} a_{n+1}=a_0\prod_{k=0}^nc_k\qquad\qquad n\geq 0 \end{align*}