2
$\begingroup$

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $a_1 = 2$ when $n \geq 2$

This is what I was thinking, \begin{align*} g(x) &= a_0x^0+a_1x^1+a_2x^2+...+a_rx^r+...\\ g(x) &= a_0 + a_1x^1 + \sum^{\infty}_{n=2}a_nx^n\\ g(x) &= 1 + 2x + \sum^{\infty}_{n=2}{(a_{n-1}+2(n-1))x^n}\\ g(x) &= 1 + 2x + \sum^{\infty}_{n=2}a_{n-1}x^n + \sum^{\infty}_{n=2}(2n-2)x^n\\ g(x) &= 1 + 2x + x\sum^{\infty}_{n=1}a_{n-1}x^{n-1} + \sum^{\infty}_{n=2}2n x^n - \sum^{\infty}_{n=2}2x^n\\ g(x) &= 1 + 2x + x\sum^{\infty}_{m=1}a_{m}x^{m} + \sum^{\infty}_{n=2}2 \binom{n}{1}x^n - \sum^{\infty}_{n=2}2x^n\\ g(x) &= 1 + 2x + x(g(x) - a_0) + \sum^{\infty}_{n=2}2 \binom{n}{1}x^n - \sum^{\infty}_{n=2}2x^n\\ \end{align*}

$\endgroup$
  • $\begingroup$ A linear recurrence relation and two initial conditions? That's strange, but easily fixable. $\endgroup$ – Jack D'Aurizio Dec 12 '18 at 3:09
  • $\begingroup$ Fixed it -- thanks! $\endgroup$ – Violet Jung Dec 12 '18 at 3:22
1
$\begingroup$

You certainly do not need generating functions for solving $a_n-a_{n-1}=2(n-1)$: it is enough to sum both sides on $n=1,2,\ldots,N$ to get that $a_n$ depends on $\sum_{k=1}^{n}2(k-1)$. The only issue in your case is that the given values of $a_0$ and $a_1$ do not agree with the given recurrence relation. So, let us assume $a_0=\color{red}{2}$ and $a_{n}=a_{n-1}+2(n-1)$ for any $n\geq 1$. By denoting as $f(x)$ the following generating function $$ f(x)=\sum_{n\geq 0} a_n x^n = 2+\sum_{n\geq 1}a_n x^n$$ we have $$ x\cdot f(x) = \sum_{n\geq 0} a_n x^{n+1} = \sum_{n\geq 1} a_{n-1} x^n $$ hence by the recurrence relation $$ (1-x) f(x) = 2+2\sum_{n\geq 1}(n-1)x^n = 2+\frac{2x^2}{(1-x)^2}$$ where the last identity follows from stars and bars in the form $$ \frac{1}{(1-x)^{m+1}}=\sum_{n\geq 0}\binom{n+m}{m}x^n.$$ Since we have $$ f(x) = \frac{2}{1-x}+\frac{2x^2}{(1-x)^3} $$ stars and bars also gives $$ a_n = [x^n]f(x) = 2-n+n^2. $$

$\endgroup$
  • $\begingroup$ I was solving the question to "Find and solve the recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper (no three circles have a common intersection point)." so I incorrectly "set" the initial values. sorry! Do you have any recommendations for what the initial conditions should be? $\endgroup$ – Violet Jung Dec 12 '18 at 3:15
  • $\begingroup$ @MathNewbie: you may just start with $a_1=2$, the linear recurrence relation and the generating function defined as a sum over $n\geq 1$. $\endgroup$ – Jack D'Aurizio Dec 12 '18 at 3:18
  • $\begingroup$ makes sense - thank you. $\endgroup$ – Violet Jung Dec 12 '18 at 3:21
  • $\begingroup$ $a_1=2$ makes sense: a circle (simple closed curve) divides the plane into two connected components (Jordan's theorem). What is debatable is to assign a value to $a_0$. $\endgroup$ – Jack D'Aurizio Dec 12 '18 at 3:29
  • $\begingroup$ Sorry, understand that now. Thanks for the clarification $\endgroup$ – Violet Jung Dec 12 '18 at 3:29

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.