Good afternoon all! This is a Saturday Afternoon/Night blog post. On the menu: much needed delicious food from Stories Cafè in Los Angeles and some work with recurrence relations.
But first, an announcement! I am working on a short series of programming tutorials of the Hewlett Packard HP 39gii Calculator. Think of it as a short boot camp to get HP 39gii owners up and running.
An emulator for the HP 39gii can be found here: http://www.hp.com/sbso/product/calculators-emulators/graphic-calculator-emulators.html. The emulators are for Widows and probably Mac - not sure if they run on other operating systems. As of today, I am not aware if there are any iOS and/or Android apps for this. I aim to post this series in March 2013.
Now on to the math...
a_(n+1) = a_n + n + C
The goal is to find a general formula for
(I) a_(n+1) = a_n + n + C with the initial condition a_0 = A_0.
The type of recursion formula presented is polynomial recurring relation. A general polynomial recursion formula takes the form a_(n+1) = a_n + p(n).
The general formula for a_(n+1) = a_n + n + C takes the form:
(II) a_n = c_2 * n^2 + c_1 * n + c_0
Mainly, with recursion formula of polynomial type will require a formula of order n+1. There are n+2 constants to solve for.
Working with equation (II) above, we will need to solve for c_0, c_1, and c_2. It would be very difficult to work with only one equation. Luckily, we can turn this problem in to a system of three linear equations.
Starting with the initial condition a_0 = A_1, we can use the recursion formula for n=1 and n=2 to find a_1 and a_2. Then we get the system:
(III)
a_0 = c_0 (where n=0)
a_1 = c_0 + c_1 + c_2 (where n=1)
a_2 = c_0 + 2 * c_1 + 4 * c_2 (where n=2)
Putting (III) in matrix form we get:
(IV)
[ [1, 0, 0], [1, 1, 1], [1, 2, 4] ] * [ [c_0], [c_1], [c_2] ] = [ [a_0], [a_1], [a_2] ]
For the Hewlett Packard HP 50g calculator owners (others may have this function/program), you can get the matrix on the left hand side of equation (IV) by using the VANDERMONDE matrix function on the vector [0, 1, 2]. This function comes in handy for these types of problems.
Continuing with the ever handy HP 50g, solving for c_0, c_1, and c_2:
(V)
[ [c_0],[c_1],[c_2] ] = [ [1, 0, 0],[-3/2, 1, -1/2],[1/2, -1, 1/2] ] * [ [a_0], [a_1], [a_2] ]
And we finish with:
(VI)
c_0 = a_0
c_1 = -3/2 * a_0 + 2 * a_1 - 1/2 * a_2
c_2 = 1/2 * a_0 - a_1 + 1/2 * a_2
So in summary:
The general formula for the recursion formula
a_(n+1) = a_n + n + C is:
c_0 = a_0
c_1 = -3/2 * a_0 + 2 * a_1 - 1/2 * a_2
c_2 = 1/2 * a_0 - a_1 + 1/2 * a_2
A numerical example:
a_(n+1) = a_n + n - 2 with a_0=3
Prepare by finding a_0, a_1, and a_2:
a_0 = 3 (given)
a_1 = 3 + 1 - 2 = 2 (use n=1)
a_2 = 2 + 2 - 2 = 2 (use n=2)
Then:
c_0 = 3
c_1 = -3/2 * 2 + 2 * 2 - 1/2 * 2 = -3/2
c_2 = 1/2 * 2 - 2 + 1/2 * 2 = 1/2
Our general formula is:
a_n = 1/2 * n^2 - 3/2 * n + 3
Let's test it out.
With n=1:
a_1 = 1/2 - 3/2 + 3 = 2 (checks out)
With n=3
a_3 = 1/2 * 3^2 - 3/2 * 3 + 3 = 3
Observe from the recursion formula a_3 = 2 + 3 - 2 = 3. (Checks out)
With n=4
a_4 = 1/2 * 4^2 - 3/2 * 4 + 3 = 5
Warning: The above technique only works when the coefficient of a_n is 1. (See (I).)
I tried this technique with a_(n+1) = -3*a_n + 7*n - 1 with a_0 =1.
With a_1 = 5 and a_2 = 0 from the recursion formula, I came up with a_n = -9/2 * n^2 + 17/2 * n + 1. Using this formula I came up with a_3 = -14, when in reality a_3 = 22. Just a heads up.
I hope this weekend and all your future days are good to you.
Eddie
This blog is property of Edward Shore. 2013