2

The relation is

$$T(n) = T(n-1)+T(n-2)-T(n-3)+1 \quad \quad (1)$$

I tried in this way but stuck at a point . Please Help

$$T(n+1) = T(n)+T(n-1)-T(n-2)+1 \quad \quad (2)$$

Subtracting $(2)$ from $(1)$ we get

$$T(n+1) = 2T(n)-2T(n-2)+T(n-3) \quad \quad (3)$$

characteristic equation is

$$r^4 -2r^3 + 2r - 1 = 0$$

$$(r-1) (r^3-r^2+r+1) = 0$$

now I am unable to find roots of cubic equation ..... Please help or suggest the correct solution. Thanks!

Stefan4024
  • 35,843
user2671993
  • 23
  • The Maple command $$rsolve(T(n) = T(n-1)+T(n-2)-T(n-3)+1, T) $$ produces $$5/4,T \left( 0 \right) +1/2,T \left( 1 \right) -3/4,T \left( 2 \right) + \left( 1/2,T \left( 2 \right) -1/2,T \left( 0 \right) \right) \left( n+1 \right)+ $$ $$\left( 1/4,T \left( 2 \right) +1/4,T \left( 0 \right) -1/2,T \left( 1 \right) \right) \left( -1 \right) ^{n}+ $$ $$1/2, \left( n+1 \right) \left( 1/2,n+1 \right) -3/8-5 /4,n-1/8, \left( -1 \right) ^{n}. $$ – user64494 Sep 13 '13 at 15:23
  • I don't get your answer how you solve it? – user2671993 Sep 13 '13 at 15:30
  • By using the rsolve command of Maple. – user64494 Sep 13 '13 at 16:30
  • You can solve the cubic equation using Cardano's method it's quite simple. – Stefan4024 Sep 13 '13 at 16:58
  • Dear user, A general rule of thumb: if in a homework question you get a polynomial you can't easily solve (and the subject of the hw is not solving difficult polynomials), then check your work! An instructor/text-book will normally take care to make sure that any auxiliary algebra that comes up in these kinds of questions is straightforward. (That is part of the skill of writing good hw/exam questions.) In any particular case, it's much more likely that you made a calculation error than that the writer of the problem included a difficult piece of algebra. Regards, – Matt E Sep 13 '13 at 18:22

1 Answers1

1

The characteristic equation $r^4-2r^3+2r-1=0$ is $(r-1)(r^3-r^2\ominus r+1)=0$ (note the minus sign denoted by $\ominus$, where you used a plus), that is $(r-1)^3(r+1)=0$.

This proves the solutions are $T(n)=A+Bn+Cn^2+D(-1)^n$ for some suitable constants $(A,B,C,D)$, and surely you can finish from here...

Did
  • 279,727
  • @ Did: But (3) is not equivalent to (1), is not so? – user64494 Sep 13 '13 at 18:21
  • No it is not, which is why you should check which solutions of (3) are solutions of (1). (Note that the initial "The characteristic equation" of my answer can only refer to (3).) – Did Sep 13 '13 at 19:03
  • @ Did: the question is about (1), is not so? – user64494 Sep 13 '13 at 19:10
  • @user64494 It happens that the proof the OP has in mind, going through (2) then through (3) then solving a characteristic equation, then deducing the solutions of (3) then checking which ones solve (1), is a perfectly valid one but that the OP was not able to go further than the characteristic equation, mainly because of a typo. So, no, the question is not only about (1). – Did Sep 13 '13 at 19:19