Posted on

Generating Function

Q:  Find the generating function for the sequence:
a0 = 1
an = 2an-1 + 1

Also, find a closed form solution for an.

A:  OK.  I am not a generating function expert, but I will try my best with the following solution and explanation:

A generating function is basically a polynomials whose coefficients represent each term of the sequence.

I am going to write out the first few terms of our sequence:
a0 = 1
a1 = 3
a2 = 7
a3 = 15
a4 = 31
….
an = 2an-1 + 1

So, we need a polynomials that looks something like:

f(x) = … + … +31x4 + 15x3 + 7x2 + 3x + 1

So:

f(x) = ∑n≥0(2n+1 – 1)xn

Write out the first few terms of this sequence to see if I am right… I am pretty sure I am, but I am trying to get this posted in a hurry (not recommended) to help out a student!

So, that is our generating function.  It “generates” the sequence.

Oh great, now he tells me the problem isn’t due for a week…. Rushed for nothing.  Oh well, I will leave it as is and if anyone doesn’t like my answer, they can challenge me to a duel.

Now for part 2:  Find a closed form solution.  Currently, each term depends on the term before it… Not good.  If you want to know the 73rd term, that means you need to know the 72nd term, which means you need to know the 71st term, which means you need to blah blah blah blah.  See why this is not good?  We want a way to find the 73rd term straight-away.

Let’s find the pattern.  I am going to start writing some terms out and doing some algebra with substitutions:

a1 = 2a0 + 1
a2 = 2a1 + 1 = 2[2a0 + 1] + 1 = 4a0 + 3
a3 = 2a2 + 1 = 2[4a0 + 3] + 1 = 8a0 + 7
a4 = 2a3 + 1 = 2[8a0 + 7] + 1 = 16a0 + 15
So, I claim that my closed form solution is:
an = 2na0 + 2n – 1

Try it.  See if it works.  What do you think?

Therefore,
a73 = 273a0 + 273 – 1

3 thoughts on “Generating Function

  1. Realized I typoed on this solution. Will fix it tonight

  2. thanks for all the help, next time I post a problem I’ll put the due date so you don’t have to rush

  3. I’m going to look this over tomorrow, I have only slept 10 hours since I got up sunday morning, thanks for everything, I’ll give it a loong look over tomorrow after work

Leave a Reply