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$
2
  • $\begingroup$ A linear recurrence relation and two initial conditions? That's strange, but easily fixable. $\endgroup$ Dec 12, 2018 at 3:09
  • $\begingroup$ Fixed it -- thanks! $\endgroup$ Dec 12, 2018 at 3:22

1 Answer 1

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$
5
  • $\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$ Dec 12, 2018 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$ Dec 12, 2018 at 3:18
  • $\begingroup$ makes sense - thank you. $\endgroup$ Dec 12, 2018 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$ Dec 12, 2018 at 3:29
  • $\begingroup$ Sorry, understand that now. Thanks for the clarification $\endgroup$ Dec 12, 2018 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.