
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(n1)4nT(n2)+(4n8)T(n3)
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 Ztransform.

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: guessandcheck, just like with differential equations. The Ztransform method operates much like the Laplace transform method (in fact, they are cousins).

I have considered this problem , it is quite tricky ,
$\displaystyle T(n)=(n+4)T(n1)4nT(n2)+(4n8)T(n3) $
$\displaystyle T(n) = n T(n1) + 4 T(n1)  4(n1) T(n2) $ $\displaystyle  4T(n2) + 4(n2)T(n3) $
$\displaystyle [T(n)  nT(n1) ]  4 [ T(n1)  (n1)T(n2) ] $ $\displaystyle + 4 [ T(n2)  (n2)T(n3) ] = 0 $
Let $\displaystyle T(n)  n T(n1) = Q(n) $
$\displaystyle Q(n)  4 Q(n1) + 4Q(n2) = 0 $
$\displaystyle Q(n) = T(n)  nT(n1) = a2^n + bn 2^n $
$\displaystyle T(0) = 2 ~,~ T(1) = 3 ~,~ T(2) = 6 $
$\displaystyle 31(2) = 2a + 2b ~,~ 62(3) = 4a + 8b $
$\displaystyle a=1 ~,~ b =  \frac{1}{2} $
Therefore , $\displaystyle T(n)  n T(n1) = 2^{n}  n 2^{n1} $ , then let $\displaystyle T(n) = 2^n + B(n) $
we have $\displaystyle B(n) + 2^n  n2^{n1}  nB(n1) = 2^n  n2^{n1} $
$\displaystyle B(n) = nB(n1) ~\implies B(n) = c n! $ when $\displaystyle n = 0 ~,~ B(0) = 1 = c $
Therefore , $\displaystyle T(n) = 2^n + n! $ as the sum of two wellknown 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 wellknown 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 intimidatingit was just so big and UGLY!!