d2jsp
Log InRegister
d2jsp Forums > Off-Topic > General Chat > Homework Help > Triangular Recurrence
Add Reply New Topic New Poll
Member
Posts: 30,945
Joined: Apr 13 2008
Gold: 11,996.69
Oct 30 2019 03:53pm
Member
Posts: 30,945
Joined: Apr 13 2008
Gold: 11,996.69
Oct 31 2019 03:43pm
Offering 1000fg if done in the next 15 hours
Member
Posts: 30,945
Joined: Apr 13 2008
Gold: 11,996.69
Oct 31 2019 05:29pm
First step:

tn = n/2 * ( n + 1 )


...
Member
Posts: 16,662
Joined: Nov 24 2007
Gold: 15,245.00
Trader: Trusted
Oct 31 2019 08:50pm
Member
Posts: 30,945
Joined: Apr 13 2008
Gold: 11,996.69
Oct 31 2019 09:48pm
Done, thanks a bunch!

1000fg sent!
Member
Posts: 16,662
Joined: Nov 24 2007
Gold: 15,245.00
Trader: Trusted
Nov 1 2019 07:55am
I missed the 'homogenous" part, I'm sorry !

With a degree 3 relationship :
We're looking for real numbers a, b, c, d such that, for every integer n :

a.t_{n+3} + b.t_{n+2} + c.t_{n+1} + d.t_n = 0

replace and expand (after multiplying by 2) :

a(n²+7n+12) + b(n²+5n+6) + c(n²+3n+2) + d(n²+n) = 0

rearrange the terms :

n² (a+b+c+d) + n(7a+5b+3c+d) + (12a+6b+2c) = 0

We just want a, b, c, d satisfying the linear homogenous system :

{ a+b+c+d = 0
{ 7a+5b+3c+d = 0
{ 12a+6b+2c = 0

Solving this leads to :

{ a = -d
{ b = 3d
{ c = -3d

We can choose d = 1, then a = -1, b = 3, and c = -3.

Finally, for every integer n :

-t_{n+3} + 3.t_{n+2} - 3.t_{n+1} + t_n = 0
Member
Posts: 5,838
Joined: Nov 19 2007
Gold: 240.00
Nov 3 2019 02:05pm
Quote (feanur @ 1 Nov 2019 04:50)


Quote (feanur @ 1 Nov 2019 15:55)
I missed the 'homogenous" part, I'm sorry !

With a degree 3 relationship :
We're looking for real numbers a, b, c, d such that, for every integer n :

a.t_{n+3} + b.t_{n+2} + c.t_{n+1} + d.t_n = 0

replace and expand (after multiplying by 2) :

a(n²+7n+12) + b(n²+5n+6) + c(n²+3n+2) + d(n²+n) = 0

rearrange the terms :

n² (a+b+c+d) + n(7a+5b+3c+d) + (12a+6b+2c) = 0

We just want a, b, c, d satisfying the linear homogenous system :

{ a+b+c+d = 0
{ 7a+5b+3c+d = 0
{ 12a+6b+2c = 0

Solving this leads to :

{ a = -d
{ b = 3d
{ c = -3d

We can choose d = 1, then a = -1, b = 3, and c = -3.

Finally, for every integer n :

-t_{n+3} + 3.t_{n+2} - 3.t_{n+1} + t_n = 0


?!

You were on the right track but this is needlessly complicated... just differentiate, just because it is discrete does not mean differentiation is not allowed.

Start with tn, the nth triangular number. Either using the formula tn=n(n+1)/2 or noticing that the nth triangular number is just 1+2+...+n, we get that t_{n)-t_{n-1}=n

Then we differentiate (I hope that's how you found the first relation): (t_{n)-t_{n-1}) - (t_{n-1)-t_{n-2}) = t_{n} - 2t_{n-1} + t_{n-2} = n - (n-1) = 1 (notice how the degree drops like in usual differentiation... though one needs to be careful, the formula for the discrete differentiation is not in general the same as the "analytic" one)

Then differentiate one last time to get the desired formula: (t_{n} - 2t_{n-1} + t_{n-2}) - (t_{n-1} - 2t_{n-2} + t_{n-3}) = t_{n} -3t_{n-1} + 3t_{n-2} -t_{n-3} = 1 - 1 = 0

This post was edited by Hanako on Nov 3 2019 02:18pm
Member
Posts: 16,662
Joined: Nov 24 2007
Gold: 15,245.00
Trader: Trusted
Nov 3 2019 06:22pm
Quote (Hanako @ Nov 3 2019 09:05pm)
?!

You were on the right track but this is needlessly complicated... just differentiate, just because it is discrete does not mean differentiation is not allowed.

Start with tn, the nth triangular number. Either using the formula tn=n(n+1)/2 or noticing that the nth triangular number is just 1+2+...+n, we get that t_{n)-t_{n-1}=n

Then we differentiate (I hope that's how you found the first relation): (t_{n)-t_{n-1}) - (t_{n-1)-t_{n-2}) = t_{n} - 2t_{n-1} + t_{n-2} = n - (n-1) = 1 (notice how the degree drops like in usual differentiation... though one needs to be careful, the formula for the discrete differentiation is not in general the same as the "analytic" one)

Then differentiate one last time to get the desired formula: (t_{n} - 2t_{n-1} + t_{n-2}) - (t_{n-1} - 2t_{n-2} + t_{n-3}) = t_{n} -3t_{n-1} + 3t_{n-2} -t_{n-3} = 1 - 1 = 0


Thanks for sharing this.

Actually, any sequence of the form : u_n = P(n) where P is a polynomial of degree d follows a linear recurrence relationship given by the characteristic equation : (r -1)^(d+1) = 0

In this case, d = 2 then (r-1)^3 = r^3 - 3r² + 3r -1 gives us the result : t_{n+3} - 3.t_{n+2} + 3.t_{n+1} - t_n = 0.
Go Back To Homework Help Topic List
Add Reply New Topic New Poll