Thread: Putnam 1990 A1

Hey guys. I was just wondering if you could help me with the following problem from the putnam exam. I've tried subtracting familure sequences from the given one, but none these sequences, once subtracted, yielded a sequence that i'm familure with.

Anyways, here is the problem T(z) means the zth term in the seqeuence

Let T(n)=(n+4)T(n-1)-4nT(n-2)+(4n-8)T(n-3)

The first few terms of this sequence are: 2. 3. 6, 14, 40, 152, 784, 4168...

Show that T(n) can be written in the form A(n)+B(n) where A, B are well known sequences.

Here is a list of sequences that I've tried thus far.

1. Catalan numbers.
2. sum of the nth row of pascal's triangle.
3. triangle numbers
4. 1, 2, 3, 4,5...
5. Powers of 2 starting with 2^0
6. Fibbonacii numbers.

The catalan numbers together with the fibbonacii numbers works for a small number of consecuitive terms, but then breaks down; together with the catalan numbers, the case is the same.

Any ideas would be appreciated.

I would probably use standard difference equation methods to solve - perhaps the Z-transform.

I don't know anything about the Z transform or standard diffrence equations, could you give me an example of diffrence equations methosd?

This is probably the simplest method of solution: guess-and-check, just like with differential equations. The Z-transform method operates much like the Laplace transform method (in fact, they are cousins).

I have considered this problem , it is quite tricky ,







Let











Therefore , , then let

we have

when

Therefore , as the sum of two well-known functions .

As this is the first problem of Putnam , i think the best way is to listen to what it said , try to express it by two well-known functions and prove it true by induction ( In fact , it is what the suggested solution's direction , I've got the book of Putnam's collections ) . My method doesn't assume it is expressible by such functions , but very straightforward ..

I don't mean to hijack this thread or anything but since we are on the topic, if I remember correctly the putnam first two questions or so are actually solvable from several angles of attack, while as you go on further and further it becomes very quite narrow and almost impossible to answer if you do not think of it the right way. Usually the solutions are very simple and elegant if you just think of it in the right way.

Nice solution SP! I was thinking about trying to play around with the reccurance relation, but it looked too intimidating--it was just so big and UGLY!!