0

Given the recurrence relation $$ T_i = T_{i-1} + 2 T_{i-2} + 2^{i - 2} - (i - 2)^2,\quad T_0 = 0,\quad T_1 = 1. $$

I need to solve it. I tried to solve the relation using generating function, but eventually I came to system of linear equations with dimension $6$.

Maybe I have to use another way to solve the relation

egreg
  • 238,574
J.Exactor
  • 215
  • If you want I can share my calculations/ – J.Exactor Nov 01 '15 at 19:34
  • Try solving the homogeneous part and combining with a particular solution. – Macavity Nov 01 '15 at 19:35
  • @Macavity Do I want to guess a particular solution? – J.Exactor Nov 01 '15 at 19:38
  • Guesswork is not needed for the functions you have. Polynomial and exponentially are handled systematically - for e.g by the method of undetermined coefficients. On a mobile so don't want to write much now, but you should be able to find on the net. – Macavity Nov 01 '15 at 19:45
  • Here is one way http://www.cwu.edu/~curtiswd/Math330-Spr13/Handouts/Handout-20-MethodOfUndeterminedCoefficients.pdf – Macavity Nov 01 '15 at 19:46
  • @Macavity. I've solved the homegeneous part. Now can I substitute it into the original relation to find a particular solution? – J.Exactor Nov 01 '15 at 19:48
  • Dimension 6 is to be expected, actually: 2 for the 2-term explicit recurrence, another 1 for the exponential additive term, and 2+1 for the degree-2 polynomial term. So I think you're on the right track. If you're looking for roots of a characteristic polynomial of degree 6, one of them will be 2 (from the exponential term) and three of them will be 1 (from the polynomial term), if that helps. – Greg Martin Nov 01 '15 at 19:49
  • Nope. You will have to assume a form for the particular solution, find it. Check the note I gave the link for. You can find particular solutions for each term and add them to the homogeneous solution in the end. – Macavity Nov 01 '15 at 19:50
  • do you exspect a simple form? – Dr. Sonnhard Graubner Nov 01 '15 at 19:53
  • @Macavity Does the particular solution looks like following: $T′_i=A2^i+Bi^2+Ci + D$ – J.Exactor Nov 01 '15 at 20:25

1 Answers1

1

The roots of the characteristic polynomial of the homogeneous part are $2$ and $-1$. To this list, we need to add $2$ again (from the exponential part of the recurrence) and $1$ three times (from the polynomial part of degree $2$). This means that the general form of the solution will be $$ T_i = (ai^2+bi+c)+(di+e)2^i+f(-1)^i $$ for some constants $a,b,c,d,e,f$. Using the first six values and solving the resulting system of linear equations yields the formula $$ T_i = \frac{i^2+i+2}{2} +\frac{3 i-14}{9} 2^{i-1} -\frac{2 }{9}(-1)^i. $$ The generating function method should work equally well and lead to the same solution.

Greg Martin
  • 78,820