Question

How can I derive closed form of polynomial recursive sequence?



Saying we have
\[\huge a_n = a_{n-1} + n^2 + 4n,\text{ where }a_0=0\] What is its closed form?

Answer 1

solve the homogenous, then solve for the particular ... difference equations are similar to differential equations

Answer 2

or, define a few terms and see if we get to a constant difference tier

Answer 3

Well, I'm not familiar with differential equations yet.

Can you show me exactly how to do second approach?

Answer 4

I'm self learning, so I may need to learn something beforehand, but I dunno.

Answer 5

the most basic approach is to list your first few terms, say 5 up to 10?

then see if we can develop the difference teirs

Answer 6

Basically like this?\[a_n = a_{n-1} + n^2+4n = a_{n-2}+(n-1)^2+4(n-1)+ n^2+4n=\cdots\]

And sorry, but exactly what is "difference teirs?"

Answer 7

the other way is to define the homogenous

\[ a_n - a_{n-1} = 0\]
and use it in determining the particular
let an = x^n
\[ x^n - x^{n-1} = 0\]
\[ x^{n-1}( x - 1) = 0~:~x=1\]
\[c_0(1)^{1}=c_1(1)^{0}+(1)^2+4(1)\]
\[c_0(1)^{2}=c_1(1)^{1}+(2)^2+4(2)\]
seems familiar

Answer 8

Um let's just stick to most basic approach because I'm lost already.

Answer 9

well, lets define the terms a0, a1, a2, a3, a4, a5, a6, .. as many as you can muster

Answer 10

By define, you mean find the value of a0, a1, a2, a3, etc?

Answer 11

yes
0 1 2 3 4 ...
0 5 17 38 70 ...

Answer 12

Ok thanks for doing calculations for me :) so what's next?

Answer 13

How many terms should I define up to?

Answer 14

0 | 5 | 17 | 38 | 70
5 12 21 32
7 9 11
2 2

take the differences, and then the differences of the differecnes, and then .... continue doing this in teirs until you come to a constant tier, one where the differences are all the same

Answer 15

ah I see

Answer 16

define a5 and see if we get to a constant of 2

11+2 = 13 +32 = 45 + 70 = 115

is a5 = 115?

Answer 17

70 + 5^2 + 4(5)

70 + 45, it is :)

Answer 18

Yeah I checked

Answer 19

now we can take the values on the front of each row and work it into a formula to find the(n-1)th term on the top

Answer 20

one way is to do a formula, im curious if we can get it this way tho

notice that if we were to represent this by a polnomial

f(x) = a + bx + cx^2 + dx^3 + ex^4 + ...

we have 3 tiers, so the thrid derivative is constant

f'''(x) = 2

f''(x) = 2x + k

f'(x) = x^2 + kx + j

f(x) = 1/3 x^3 + 1/2 kx^2 + jx + m
-------------------------------

f(0) = 0, so m=0
------------------------

f(1) = 5 = 1/3 + 1/2 k + j
------------------------

f(2) = 17 = 1/3 (2^3) + 1/2 k (2^2) + 2j
-----------------------

think thisll work? 2 equations in 2 unknowns?

Answer 21

Hmm interesting... Give me couple mins to solve for unknowns.

Answer 22

I got \(k=5\) and \(j=\dfrac{13}{6}\)

So closed form would be \(f(n)=\boxed{a_n=\dfrac{1}{3}n^3+\dfrac{5}{2}n^2+\dfrac{13}{6}n}\)

Checking: from closed form, \(a_6 = 175\); from recursive form, \(a_6 = 115 + 6^2 + 4(6) = 175\)

It seems to work. Awesome!

Answer 23

I'm surprised to see that coefficients are ugly fraction, yet it will always result as integer for \(n\in\mathbb N\)

Answer 24

yeah, i even impressed myself :)

i know that differences are related to derivatives, so i took a stab at it

Answer 25

Awesome. Leveled up: math skill: +1 thanks to you! :)

Answer 26

youre welcome :)