Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find generating function for the recurrence:

  • $a_0 = 1$,
  • $a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$.

It looks like this:

  • $a_0 = 1$
  • $a_1 = {1 \choose 2} + 3$
  • $a_2 = {2 \choose 2} + 3{1 \choose 2} + 9$
  • $a_3 = {3 \choose 2} + 3{2 \choose 2} + 9{1 \choose 2} + 27$
  • $a_4 = {4 \choose 2} + 3{3 \choose 2} + 9{2 \choose 2} + 27 {1 \choose 2} + 81$

I know what the generating function of the sequence $3 ^n = (1, 3, 9, 27, 81, \dots)$ is, as well as what the generating functions for some sequences of combinatorial numbers are, but how do I split the sequence up into these pieces I know?

(The problem is those combinatorial numbers "move right" every time. If they were growing left-to-right along with their coefficients, it would be much easier. And there is no constant difference between $a_i$ and $a_{i + 1}$.)

share|improve this question
2  
You should first write $a_n$ as a function of $n$ and then see what it can look like. In your case: $$\displaystyle a_n=3^n+\sum_{k=0}^{n-1}3^k{n-k \choose 2}$$ –  Dolma Apr 25 '13 at 13:15
add comment

5 Answers

up vote 1 down vote accepted

A related problem. Assume $ F(x) = \sum_{n=0}^{\infty}a_n x^n $, then $$ a_n = {n \choose 2} + 3a_{n - 1} \implies a_{n+1} = {n+1 \choose 2} + 3a_{n}$$

$$ \sum_{n=0}^{\infty} a_{n+1} x^n = \frac{1}{2}\sum_{n=0}^{\infty}n(n+1)x^n + 3\sum_{n=0}^{\infty}a_{n}x^n $$

$$ \implies \sum_{n=1}^{\infty} a_{n} x^{n-1} = \frac{1}{2}\sum_{n=1}^{\infty}nx^{n}+\frac{1}{2}\sum_{n=1}^{\infty}n^2x^{n} +3F(x) $$

$$ \implies \frac{1}{x}F(x)-\frac{a_0}{x}-3F(x) = \frac{1}{2}\sum_{n=1}^{\infty}nx^{n}+\frac{1}{2}\sum_{n=1}^{\infty}n^2x^{n} $$

$$\implies \left(\frac{1}{x}-3 \right)F(x)=\frac{1}{x}+\frac{1}{2}\frac{x}{(x-1)^2}-\frac{1}{2}\frac{x(x+1)}{(x-1)^3} $$

$$ \implies \left(\frac{1}{x}-3 \right)F(x)=\frac{1}{x}-\frac{x}{(x-1)^3} $$

$$ \implies F(x)=\frac{x}{1-3x}\left( \frac{1}{x}-\frac{x}{(x-1)^3} \right). $$

share|improve this answer
    
At the third line of the block of equations, you have changed the sums to start at $n = 1$ instead of $n = 0$. If I understood it correctly, you just rewrote those sums from the previous line. But then $$\frac{1}{2}\sum_{n = 0}^\infty {n(n + 1)x^n}$$ turns into $$\frac{1}{2}\sum_{n = 1}^\infty {(n - 1)n x^{n - 1}} = \frac{1}{2}\sum_{n = 1}^\infty {nx^{n-1}} - \frac{1}{2}\sum_{n = 1}^\infty {n^2x^{n-1}}$$. What is wrong? –  David Čepelík Apr 26 '13 at 8:13
    
Huh, I see now. Both $n^2$ and $n$ are $0$ for $n = 0$. Sorry –  David Čepelík Apr 26 '13 at 13:34
    
Mhenni, it took me a long time to figure out what you were doing, but finally, I got it! Thanks a lot! –  David Čepelík Apr 26 '13 at 20:41
    
@David: You are welcome. All of us spend long time to understand things. It is natural. Good luck. –  Mhenni Benghorbal Apr 26 '13 at 20:50
add comment

Let $A(x)=\sum_{n=0}^\infty a_nx^n$. Then \begin{eqnarray} A(x)&=&1+\sum_{n=1}^\infty a_{n}x^n\\ &=&1+\sum_{n=1}^\infty (3a_{n-1}+\frac{1}{2}n(n-1))x^n\\ &=&1+3xA(x)+\frac{1}{2}\sum_{n=1}^\infty n(n-1)x^n. \end{eqnarray} Note $\sum_{n=0}^\infty x^n=\frac{1}{1-x}$ for $|x|<1$. Differentiating this twice, you can give $$ \sum_{n=2}^\infty n(n-1)x^{n-2}=\frac{2}{(1-x)^3}. $$ Thus $$ A(x)=1+3xA(x)+\frac{x^2}{(1-x)^3} $$ from which you can get $A(x)$.

share|improve this answer
    
Could you please explain to me what is the point of differentiating the equation? I get lost reading the second half of the answer. –  David Čepelík Apr 25 '13 at 14:06
    
Differentiating $\sum_{n=0}^\infty x^n=\frac{1}{1-x}$, you can get $\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}$. Differentiating $\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}$, you can get $\sum_{n=2}^\infty n(n-1)x^{n-2}=\frac{2}{(1-x)^3}$. –  xpaul Apr 25 '13 at 14:39
    
I see. I have never seen this before, so that's what confused me. –  David Čepelík Apr 25 '13 at 14:43
add comment

Hint Let $F:=\sum_0^\infty a_n x^n$. Consider $a_n x^n= 3 a_{n-1}x^{n}+C_n^2 x^n$.

share|improve this answer
add comment

As I said in my comment, you have:

$$\displaystyle a_n=3^n+\sum_{k=0}^{n-1}3^k{n-k \choose 2}$$

You can rewrite this as:

$$\displaystyle a_n=3^n+\sum_{k=1}^{n}3^{n-k}{k \choose 2}=3^n+3^n\sum_{k=1}^{n}3^{-k}{k \choose 2}=3^n\left(1+\sum_{k=1}^{n}\left(\frac{1}{3}\right)^{k}{k \choose 2}\right)$$

Also you have:

$$\displaystyle\sum_{k=1}^\infty \left(\frac{1}{3}\right)^{k}{k \choose 2}=\sum_{k=0}^\infty \left(\frac{1}{3}\right)^{k}{k \choose 2}=\dfrac{\left(\frac{1}{3}\right)^{2}}{\left(1-\frac{1}{3}\right)^{3}}=\frac{3}{8}$$

share|improve this answer
add comment

Sneaky. Write your recurrence without subtractions in indices, i.e.: $$ a_{n + 1} = 3 a_n + \binom{n + 1}{2} $$ Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums, particularly: \begin{align} \sum_{n \ge 0} \binom{n + 1}{2} z^n &= z \sum_{n \ge 0} \binom{n + 1}{2} z^{n - 1} \\ &= z \sum_{n \ge 0} \binom{n + 2}{2} z^n \\ &= \frac{z}{(1 - z)^3} \end{align} so that: $$ \frac{A(z) - a_0}{z} = 3 A(z) + \frac{z}{(1 - z)^3} $$ Using $a_0 = 1$ and solving as partial fractions: $$ A(z) = \frac{11}{8 (1 - 3 z)} - \frac{1}{2 (1 - z)^3} + \frac{1}{4 (1 - z)^2} - \frac{1}{8 (1 - z)} $$ We can read off the coefficients here: \begin{align} a_n &= \frac{11}{8} \cdot 3^n - \frac{1}{2} \binom{-3}{n} (-1)^n + \frac{1}{4} \binom{-2}{n} (-1)^n - \frac{1}{8} \\ &= \frac{11 \cdot 3^n - 1}{8} - \frac{1}{2} \binom{n + 3 - 1}{3 - 1} + \frac{1}{4} \binom{n + 2 - 1}{2 - 1} \\ &= \frac{11 \cdot 3^n - 1}{8} - \frac{1}{2} \cdot \frac{(n + 2) (n + 1)}{2!} + \frac{1}{4} \cdot \frac{n + 1}{1!} \\ &= \frac{11 \cdot 3^n - 2 n^2 - 4 n - 3}{8} \end{align}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.