Generating function, recurrence with sum

Question

I have the following recurrence:

$a_0 = \frac{1}{2} $, $a_n = 1 - \frac{2}{3}\sum_{k=0}^{n-1} a_k$ for $n \ge 1$

My steps so far:

$$A(x) = \sum_{n=0}^\infty a_nx^n$$

$$a_n = 1 - \frac{2}{3}\sum_{k=0}^{n-1}a_k$$ $$ a_n = 3 - 2\sum_{k=0}^{n-1}a_k $$

$$\sum_{n=1}^\infty a_nx^n = \sum_{n=1}^\infty 3x^n -\sum_{n=1}^\infty \sum_{k=0}^{n-1} 2a_kx^n$$

$$A(x) - \frac{1}{2} = 3 \cdot (\frac{x}{1-x}) - \sum_{n=1}^\infty \sum_{k=0}^{n-1} 2a_kx^n $$

But now I don't know what to do with the double summation? How do I simplify it?

// Edit Thanks to Anshumaan Mishra answer I made a few more steps

$$A(x) = \sum_{n=0}^\infty a_nx^n$$

$$ 3a_{n+1} = a_n$$

$$ \sum_{n=1}^{\infty}a_nx^n = 3 \sum_{n=1}^{\infty}a_{n+1}x^n $$

I'm not sure how to further convert that.

$$ 3 \sum_{n=1}^{\infty}a_{n+1}x^n $$ Do we want to subtract the first term like:

$$ \stackrel{?}{=} 3 \sum_{n=1}^{\infty}(a_{n}x^n) - \frac{1}{2} $$

Answer 1

I believe the question can be better interpreted if we manipulate the general term expression by expressing $\sum_{k=0}^{n-1} a_{k} $ in terms of $a_{k-1}$ as: $$a_{n} = 1-\frac{2}{3}\sum_{k=0}^{n-1}a_{k}$$ $$1-a_{n} = \frac{2}{3}\sum_{k=0}^{n-1}a_{k}$$ $$\frac{3}{2}(1-a_{n}) =\sum_{k=0}^{n-1}a_{k}$$ We will use this to evaluate the value of $\sum_{k=0}^{n}a_{k} $ $$\sum_{k=0}^{n}a_{k} = a_n + \sum_{k=0}^{n-1}a_{k}$$ $$\sum_{k=0}^{n}a_{k} = a_n + \frac{3}{2}(1-a_{n}) $$ $$\sum_{k=0}^{n}a_{k} = \frac{3}{2}-\frac{1}{2}a_{n} $$ Now putting the values in the general term for $a_{n+1}$ $$a_{n+1} = 1-\frac{2}{3}\sum_{k=0}^{n}a_{k}$$ $$a_{n+1} = 1-\frac{2}{3}(\frac{3}{2}-\frac{1}{2}a_{n})$$ $$a_{n+1} = \frac{1}{3}a_{n}$$

Now this series can be converted into a GP. But since we used the value of $a_{n-1}$ in the expression for $a_n$, the sum should be evaluated from $1$ to $n$ and the value of $a_0$ should be added as required.

Sorry for latex errors as I am not well versed in the language.

Edit: From my understanding of generative functions: $$f(x)= \frac{1}{2}+\frac{2x}{3}+\frac{2x^2}{3^2}\cdots\frac{2x^n}{3^n}$$ $$f(x)= 2+\frac{2x}{3}+\frac{2x^2}{3^2}\cdots\frac{2x^n}{3^n}-\frac{3}{2}$$ $$f(x)=2\sum_{r=0}^{n}{(\frac{x}{3})^r}-\frac{3}{2}$$ $$f(x)=2\frac{1-\frac{x^{n+1}}{3^{n+1}}}{1-\frac{x}{3}}-\frac{3}{2}$$

Answer 2

I will use the result of Anshumaan to provide a solution using ordinary generating functions.

We define our generating function as $$ F(x)= \sum_{n\geqq 0}a_nx^n $$ $a_{n+1}=\frac{1}{3}a_n$ Multiplying by $x^n$ and summing up gives:

$$\sum_{n\geqq 0}a_{n+1}x^n=\frac{1}{3}\sum_{n\geqq 0}a_nx^n$$

Writing this in terms of $F(x)$ gives $$ F(x)=\frac{3}{6-2x}$$ Which expands as: $$ F(x)= \sum_{n=0}^{\infty} \frac{1}{2} \frac{1}{3^{n}}x^n $$

Answer 3

I am a bit late to the party and, even if Anshumaan Mishra's great answer has been already accepted, here is an interesting alternative derivation for a direct computation of the generating function, which doesn't require the intermediate step where the sequence $(a_n)_n$ is found to be of geometric nature.

It goes as follows : $$ \begin{align} A(x) &= \sum_{n=0}^\infty a_nx^n \\ &= a_0 + \sum_{n=1}^\infty a_nx^n \\ &= a_0 + \sum_{n=1}^\infty \left(1-\frac{2}{3} \sum_{k=0}^{n-1} a_k\right)x^n \\ &= a_0 + \sum_{n=1}^\infty x^n - \frac{2}{3} \sum_{n=1}^\infty\sum_{k=0}^{n-1} a_kx^n \\ &= a_0 + \left(\frac{1}{1-x} - 1\right) - \frac{2}{3} \sum_{n=0}^\infty\sum_{k=0}^n a_kx^{n+1} \\ &= a_0 + \frac{x}{1-x} - \frac{2}{3}x \sum_{n=0}^\infty\sum_{k=0}^n a_kx^n \end{align} $$ Then, the double sum can be tackled by inverting the order of summation in the following way : $$ \begin{align} \sum_{n=0}^\infty\sum_{k=0}^n a_kx^n &= \sum_{k=0}^\infty\sum_{n=k}^\infty a_kx^n \\ &= \sum_{k=0}^\infty\sum_{n=0}^\infty a_kx^{n+k} \\ &= \sum_{k=0}^\infty a_kx^k \sum_{n=0}^\infty x^n \\ &= \frac{A(x)}{1-x} \end{align} $$ Plugging this result back into the first equation, one gets : $$ A(x) = a_0 + \frac{x}{1-x}\left(1-\frac{2}{3}A(x)\right) $$ hence finally $$ A(x) = \frac{a_0 + \frac{x}{1-x}}{1+\frac{2}{3}\frac{x}{1-x}} = \frac{(1-x)a_0 + x}{1 - \frac{1}{3}x} $$

Answer 4

We consider the recurrence relation \begin{align*} \color{blue}{a_n}&\color{blue}{=1-\frac{2}{3}\sum_{k=0}^{n-1}a_k\qquad\qquad n\geq 1}\tag{1}\\ \color{blue}{a_0}&\color{blue}{=\frac{1}{2}} \end{align*} and are looking for a generating function \begin{align*} A(x)=\sum_{n=0}^{\infty}a_nx^n\tag{2} \end{align*} Subtracting in (1) from both sides $\frac{2}{3}a_n$ and multiplying the equation by $3$ we can write the recurrence relation (1) as \begin{align*} \color{blue}{a_n}&\color{blue}{=3-2\sum_{k=0}^na_k\qquad\qquad n\geq 1}\tag{3}\\ \color{blue}{a_0}&\color{blue}{=\frac{1}{2}} \end{align*}

We obtain from (2) and (3) \begin{align*} \sum_{n=1}^{\infty}a_nx^n&=3\sum_{n=1}^{\infty}x^n-2\sum_{n=1}^{\infty}\sum_{k=0}^na_kx^n\\ A(x)-a_0&=\frac{3x}{1-x}-2\left(\sum_{n=0}^{\infty}\sum_{k=0}^na_k-a_0\right)\\ A(x)-\frac{1}{2}&=\frac{3x}{1-x}-2\left(\frac{1}{1-x}A(x)-\frac{1}{2}\right)\tag{4}\\ A(x)\left(1+\frac{2}{1-x}\right)&=\frac{3x}{1-x}+\frac{3}{2}\\ \color{blue}{A(x)}&\color{blue}{=\frac{3}{2}\left(\frac{1+x}{3-x}\right)} \end{align*} We can also write the generating function $A(x)$ as \begin{align*} \color{blue}{A(x)}&\color{blue}{=\frac{3}{2}\left(\frac{1+x}{3-x}\right)}=\frac{1}{2}+\frac{2x}{3-x} =\frac{1}{2}+2\left(\frac{\frac{x}{3}}{1-\frac{x}{3}}\right)\\ &=\frac{1}{2}+2\sum_{n=1}^{\infty}\frac{1}{3^n}x^n\\ &\,\,\color{blue}{=\frac{1}{2}+\frac{2}{3}x+\frac{2}{9}x^2+\frac{2}{27}x^3+\cdots} \end{align*}

Comment:

• In (4) we use that multiplication of a series $A(x)$ with $\frac{1}{1-x}$ results in summing up the coefficients, since \begin{align*} \frac{1}{1-x}A(x)&=\sum_{l=0}^{\infty}x^l\sum_{k=0}^{\infty}a_kx^k\\ &=\sum_{n=0}^{\infty}\left(\sum_{{k+l=n}\atop{k,l\geq 0}}a_k\right)x^n\\ &=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_k\right)x^n \end{align*}