olymmath

Putnam 1990 A1

  • Session A

Let T0=2,T1=3,T2=6,T_0 = 2, T_1 = 3, T_2 = 6, and for n≥3n \geq 3, Tn=(n+4)Tn−1−4nTn−2+(4n−8)Tn−3.T_n = (n+4)T_{n-1} - 4n T_{n-2} + (4n-8) T_{n-3}. The first few terms are 2,3,6,14,40,152,784,5168,40576.2, 3, 6, 14, 40, 152, 784, 5168, 40576. Find, with proof, a formula for TnT_n of the form Tn=An+BnT_n = A_n + B_n, where {An}\{A_n\} and {Bn}\{B_n\} are well-known sequences.

Curated text Kedlaya Putnam archive. Quoted with source.

Solutions

Human solution Solution 1 by Tahir Imanov

Tn=2n+n!T_n = 2^n + n! is true for n=0,1,2n=0,1,2. Let's assume it is also true for n=k,k+1,k+2n=k,k+1,k+2 where,

  • Tk=2k+(k)!T_{k} = 2^{k} + (k)!
  • Tk+1=2k+1+(k+1)!T_{k+1} = 2^{k+1} + (k+1)!
  • Tk+2=2k+2+(k+2)!T_{k+2} = 2^{k+2} + (k+2)!.

Then, let's prove it for n=k+3.

Using   Tn=(n+4)Tn−1−4nTn−2+(4n−8)Tn−3\; T_n = (n+4) T_{n-1} -4n T_{n-2} + (4n-8)T_{n-3}, we get

Tk+3=(k+7)⋅2k+2+(k+7)(k+2)!−(k+3)⋅2k+3−4(k+3)(k+1)!+(k+1)⋅2k+2+4(k+1)!==2k+2(k+7−2k−6+k+1)+(k2+9k+14−4k−12+4)(k+1)!==2k+2⋅2+(k2+5k+6)(k+1)!=2k+3+(k+3)!T_{k+3} = (k+7) \cdot 2^{k+2} + (k+7)(k+2)! - (k+3) \cdot 2^{k+3} - 4(k+3)(k+1)! + (k+1) \cdot 2^{k+2} + 4(k+1)! = \\ = 2^{k+2} (k+7 - 2k - 6 + k + 1) + (k^2 +9k+14 -4k -12 + 4) (k+1)! = \\ = 2^{k+2} \cdot 2 + (k^2 +5k+6)(k+1)! = 2^{k+3} + (k+3)!

Case closed....


Irrelevant PS.
Tk+1−Tk=2k+k⋅k!=Tk+(k−1)k!  ⇒Tk+1=2Tk+(k−1)k!T_{k+1} - T_k = 2^k + k \cdot k! = T_k + (k-1)k! \; \Rightarrow T_{k+1} = 2T_k + (k-1)k!


Just came to mind:
Using   Tn=(n+4)Tn−1−4nTn−2+(4n−8)Tn−3\; T_n = (n+4) T_{n-1} -4n T_{n-2} + (4n-8)T_{n-3} we get
Tn−2Tn−1=(n+2)(Tn−1−2Tn−2)−(2n−4)(Tn−2−2Tn−3)T_n - 2T_{n-1} = (n+2)(T_{n-1} - 2T_{n-2}) - (2n-4)(T_{n-2} - 2T_{n-3})
Let's assume An=Tn−2Tn−1A_n = T_n - 2T_{n-1}, we get
An=(n+2)An−1−(2n−4)An−2        for    n≥3.A_n = (n+2)A_{n-1} - (2n-4)A_{n-2} \; \; \; \; for \; \; n \ge 3.
An=−1,0,2,12,.....A_n = -1, 0, 2, 12, .....

Mathematics Stack Exchange. Open licence.

Similar problems

These problems have the most words in common with this statement.

Locator putnam/1990/a1 · Tag E44CE5Z7H2 · Edit this page on GitHub · Keys: j next, k previous