Putnam 1990 A1

• Jun 19th 2010, 04:05 PM
Chris11
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.
• Jun 19th 2010, 04:53 PM
Ackbeet
I would probably use standard difference equation methods to solve - perhaps the Z-transform.
• Jun 19th 2010, 05:48 PM
Chris11
I don't know anything about the Z transform or standard diffrence equations, could you give me an example of diffrence equations methosd?
• Jun 19th 2010, 06:05 PM
Ackbeet
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).
• Jun 19th 2010, 08:49 PM
simplependulum
I have considered this problem , it is quite tricky ,

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

$T(n) = n T(n-1) + 4 T(n-1) - 4(n-1) T(n-2)$ $- 4T(n-2) + 4(n-2)T(n-3)$

$[T(n) - nT(n-1) ] - 4 [ T(n-1) - (n-1)T(n-2) ]$ $+ 4 [ T(n-2) - (n-2)T(n-3) ] = 0$

Let $T(n) - n T(n-1) = Q(n)$

$Q(n) - 4 Q(n-1) + 4Q(n-2) = 0$

$Q(n) = T(n) - nT(n-1) = a2^n + bn 2^n$

$T(0) = 2 ~,~ T(1) = 3 ~,~ T(2) = 6$

$3-1(2) = 2a + 2b ~,~ 6-2(3) = 4a + 8b$

$a=1 ~,~ b = - \frac{1}{2}$

Therefore , $T(n) - n T(n-1) = 2^{n} - n 2^{n-1}$ , then let $T(n) = 2^n + B(n)$

we have $B(n) + 2^n - n2^{n-1} - nB(n-1) = 2^n - n2^{n-1}$

$B(n) = nB(n-1) ~\implies B(n) = c n!$ when $n = 0 ~,~ B(0) = 1 = c$

Therefore , $T(n) = 2^n + n!$ 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 ..
• Jun 20th 2010, 09:58 AM
gmatt
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.
• Jun 20th 2010, 10:23 AM
Chris11
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!!