Exponential Generating Function Fun

307 Views Asked by At

Given the recurrence relation of $a_n = a_{n-1} + n$, for $n \gt 0$, Where $a_0 = 1$.

I know the solution is: $a_n = \frac{1}{2}n^2 + \frac{1}{2}n + 1$.

I am not having troubles finding this solution, however, I am having troubles acquiring the solution by means of what the question is asking for.

I need to answer this question using only an Exponential Generating Function. Any help would be greatly appreciated.

1

There are 1 best solutions below

2
On BEST ANSWER

Write $$A(x)=\sum_{n=0}^\infty a_n\frac{x^n}{n!}\ .$$ Then $$\eqalign{A(x) &=1+\sum_{n=1}^\infty(a_{n-1}+n)\frac{x^n}{n!}\cr &=1+\sum_{n=1}^\infty \frac{x^n}{(n-1)!} +\sum_{n=0}^\infty a_n\frac{x^{n+1}}{(n+1)!}\cr &=1+xe^x+\sum_{n=0}^\infty a_n\frac{x^{n+1}}{(n+1)!}\ .\cr}$$ Differentiating both sides leads to the differential equation $$\frac{dA}{dx}-A=(x+1)e^x\ ,$$ and solving with the initial condition $A(0)=1$ gives $$A=(1+x+\tfrac12x^2)e^x\ .$$ Extracting the coefficient of $\frac{x^n}{n!}$ gives the answer.

I'll leave you to fill in the working.