To show you how this works:

Supposing you had this question.

Is a(n) an integer for all n?

You cannot solve the recurrence, so you use it to generate some numbers. This is a typical procedure for experimental math.

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188...

Looks like they will all be integers but we would like to be a little bit more certain of that. Copy the sequence and go here:

Paste the sequence into the top box and you get:

The Motzkin numbers! A well known combinatoric sequence.

So you look them up:

http://mathworld.wolfram.com/MotzkinNumber.html

You see that the Motzkin numbers count the number of paths through a lattice. They are always integers. You cannot have 2.8 paths from some point to another on a lattice.

Then you look further and see the recurrence for the Motzkin numbers. If you take that recurrence and substitute n = n-1 into ours ( just a shift of indices ), it becomes that recurrence. We are done!

]]>