All I know is that x = 1 is a root of the polynomial, but I don't know what to do next.

Consider the sequence of integers $$ a_{n} $$ for $$ n \geq 0 $$ defined recursively as follows:\

$$ a_{0}=a_{1}=a_{2}=0; a_{3}=1. $$\

For $$ n \geq 4, $$\
$$ a_{n} = 6a_{n-1}-11a_{n-2}+6a_{n-3} $$\
Find a closed formula for $$ a_{n} $$ (Note that x = 1 is a root of the polynomial $$ 6x^3-11x^2+6x-1.) $$\

Question

All I know is that x = 1 is a root of the polynomial, but I don't know what to do next.

Consider the sequence of integers $$ a_{n} $$ for $$ n \geq 0 $$ defined recursively as follows:\

$$ a_{0}=a_{1}=a_{2}=0; a_{3}=1. $$\

For $$ n \geq 4, $$\
$$ a_{n} = 6a_{n-1}-11a_{n-2}+6a_{n-3} $$\
Find a closed formula for $$ a_{n} $$ (Note that x = 1 is a root of the polynomial $$ 6x^3-11x^2+6x-1.) $$\

kainui · Answer

Latex broken? Can you repost it as a comment

usukidoll · Answer

efff latex is dead in here -_-

usukidoll · Answer

Consider the sequence of integers $$ a_{n} $$ for $$ n \geq 0 $$ defined recursively as follows:\

$$ a_{0}=a_{1}=a_{2}=0; a_{3}=1. $$\

For $$ n \geq 4, $$\
$$ a_{n} = 6a_{n-1}-11a_{n-2}+6a_{n-3} $$\
Find a closed formula for $$ a_{n} $$ (Note that x = 1 is a root of the polynomial $$ 6x^3-11x^2+6x-1.) $$\

usukidoll · Answer

either I have amnesia or I really don't know how this works... but I know that x = 1 is a root

kainui · Answer

Oh you could solve this with generating functions it looks like that's how they're wanting you to solve it maybe. At least you can factor out (x-1) from that polynomial maybe to turn it into like partial fraction decomposition if that makes sense to you. I'm gone for mothers day stuff now, good luck in the mean time!

usukidoll · Answer

like finding all roots to that polynomial?

kainui · Answer

Ok so things are slow to start right now, so we're good, define this sequence:

$$S(x) = \sum_{n=0}^\infty a_n x^n$$$$S(x) = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+\cdots$$
Now if you add this thing to itself, but shifted and multiplied, you'll end up with the recurrence relation.

$$S(x) = \text{some extra terms}+ 6xS(x)-11x^2S(x)+6x^3S(x)$$

The extra terms come out of shifting the polynomials over to get them to cancel out, then you can factor and use partial fraction decomposition to get a simpler closed form probably. I gotta go for real this time though so good luck haha

usukidoll · Answer

:S  so that can be used to find the remaining roots.. maybe I should search recurrence relation first haha  (3x-1)(2x-1)(x-1) x = 1, 1/2, 1/3

usukidoll · Answer

:S!

kainui · Answer

OK so did you get anywhere or are you still sorta flopping around on this

kainui · Answer

Ok to be fair maybe that's a loaded question hahaha I wouldn't've known what to do if I didn't have someone show me this trick either. I learned it in this book called 'generatingfunctionology' so let's get to it.

kainui · Answer

The idea is this, start here by defining this object for ourselves:
$$S(x) = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+\cdots$$
Now what we do is we play around with this by some tricks, so that by adding this thing to itself we end up getting it to simplify due to the recursion relation we were given,
$$a_n = 6a_{n-1} - 11 a_{n-2}+6a_{n-3}$$
So as a specific example, we'd want when n=4
$$a_4=6a_3-11a_2+6a_1$$
It's all about writing the sum the right way so that it matches up to follow a pattern. So try to figure out, what do you have to multiply S(x) by to make it so that you get those terms to line up like that? The idea is by multiplying by a power of x, you shift the terms around. For instance side example:

$$T(x) = b_0+b_1x+b_2x^2+\cdots$$
$$2xT(x)=2b_0x+2b_1x^2+2b_2x^3+\cdots$$
combined gives:
$$T(x)+2xT(x) = b_0 + (b_1+2b_0)x+(b_2+2b_1)x^2+\cdots$$

usukidoll · Answer

are we getting a telescoping series out of this?

kainui · Answer

no, we're getting a recurrence relation outta it. Look at each coefficient as being a specific version of the recurrence relation you are looking for in general

usukidoll · Answer

so if n = 4 what our result should be is
$$a_{4} =6a_{3}-11a_{2}+6a_{1}$$
we are given that
a_0=a_1=a_2=0 and a_3 = 1

so a_4 should be 6 by itself. ?!

kainui · Answer

Well, relax for a second on that, we'll sorta have to treat the initial terms separately but we'll come to that

kainui · Answer

Pretend the initial stuff doesn't matter for now, all I want you to do is come up with a way write it so that the terms add up the right way. Find the things to multiply S(x) by so that you get the recurrence relation you need

usukidoll · Answer

I could have one as x and then another as 5x but adding that together will be 6x and that would only work for the first and third terms sinc e both are 6