×

# algorithm 4

Solve the recurrence an=3an−1−3an−2+an−3for n>2 with a0=a1=0 and a2=1. Solve the same recurrence with the initial condition on a1 changed to a1=1.

Note by Pryhant Kielh
3 years, 3 months ago

Sort by:

First recurrence:

$a(n)=\frac{1}{2} \left(n^2-n\right)$

Second recurrence:

$a(n)=\frac{1}{2} \left(3 n-n^2\right)$ · 3 years, 3 months ago

Hi;

If this is the recurrence

$a(n) = 3 a(n - 1)- 3 a(n - 2) + a(n - 3)$

then there are many methods. perhaps the simplest is by using the techniques of experimental math.

Generate the first couple of terms

0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66,...

if you do not recognize that sequence then take it over to the the OEIS. This is a tremendous online resource available to everyone so why "Rediscover America"

[a_n=\frac{1}{2} \left(n^2-n\right)/] · 3 years, 3 months ago

Sorry, bad latexing: $a_n=\frac{1}{2} \left(n^2-n\right)$ · 3 years, 3 months ago