Results 1 to 7 of 7

Math Help - Putnam 1990 A1

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I would probably use standard difference equation methods to solve - perhaps the Z-transform.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    I don't know anything about the Z transform or standard diffrence equations, could you give me an example of diffrence equations methosd?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 ..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2009
    Posts
    95
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Putnam Problem of the Day
    Posted in the Math Puzzles Forum
    Replies: 6
    Last Post: August 13th 2010, 09:32 PM
  2. Putnam Problem of the Day (3)
    Posted in the Math Challenge Problems Forum
    Replies: 6
    Last Post: June 11th 2010, 01:31 AM
  3. Putnam Problem of the Day (2)
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: May 24th 2010, 05:21 PM
  4. Help needed on IMO 1990 question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: March 28th 2009, 06:36 AM
  5. Putnam proof
    Posted in the Statistics Forum
    Replies: 8
    Last Post: August 31st 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum