Question

Non-homogeneous recurrence solving. Need help with beginning.

Question: tn = 2t(n-1) + n^2
The n of tn and 2t(n-1) is subscripted

In my notes I need to find the characteristic equation first. All the examples say I need to start with the form tn - t(n-1) = 3^n <- always x^n on right side

Here I made the equation into:

tn - 2t(n-1) = n^2

n^2 isn't of exponent n and I'm unsure if this is a problem. The next steps include eliminating the right side by replacing the n with n-1 and multiplying the equation such that you can cancel the right side out by subtracting the original eq

Answer 1

\[t_n-c t_{n-1}=f(n) \\ u_{n}t_n-c u_{n}t_{n-1}=f(n) u_{n} \text{ multiply both sides by } u_{n} \\ \\ \text{ this is a sequence of my choice } \ \text{ Let } c u_n=u_{n-1} \\ \\ c=\frac{u_{n-1}}{u_n} \\ \text{ product of both sides } \\ c \cdot c \cdot c \cdots c=\frac{u_0}{u_1} \cdot \frac{u_1}{u_2} \cdot \frac{u_2}{u_3} \cdots \frac{u_{n-1}}{u_n} \\ \\ c^n=\frac{u_0}{u_n} \\ u_n=u_0 c^{-n}\]

So let's back up a little...
\[u_n t_n-u_{n-1}t_{t-1}= f(n)u_n \\ \\ \text{ sum both sides from } n=1 \text{ to } n=N \\ (u_1 t_1-u_0t_0)+(u_2 t_2-u_1 t_1)+(u_3t_3-u_2 t_1)+ \cdots +(u_N t_N-u_{N-1}t_{N-1}) \\ = \sum_{n=1}^{N} f(n) u_n \\ \implies -u_0 t_0+u_N t_N =\sum_{n=1}^{N} f(n) u_n \\ \implies u_N t_N= \sum_{n=1}^{N} f(n) u_n+u_0 t_0\]


So pluggin u(n) we have and solving for t(N)...
\[t_N= \frac{1}{u_{N}}( \sum_{n=1}^{N} f(n) u_n +u_0 t_0 )\\ t_N=\frac{c^{N}}{u_0} (\sum_{n=1}^{N} f(n) u_0 c^{-n}+u_0t_0) \\ t_N= c^{N} (\sum_{n=1}^{N} f(n) c^{-n} +t_0) \\ t_N= c^{N} \sum_{n=1}^N (f(n) c^{-n}) +c^N t_0\]

Answer 2

though you could also use undetermined coefficient way ... that above sum may be easy to simplify depending on f(n) could be hard though

Answer 3

not sure what you mean with n^2 thingy you wrote

Answer 4

I don't know what steps you are trying to describe either

Answer 5

example say f(n)=n and c=1
so we have
\[t_N=1^{N} \sum_{n=1}^{N} (n 1^{-n})+1^{N} t_0 \\ t_N=\sum_{n=1}^{N} n+t_0 \\ t_N=\frac{N(N+1)}{2}+t_0 \\ \text{ replace }N \text{ with } n \\ t_n=\frac{n(n+1)}{2}+t_0 \text{ this is solution to } t_n-t_{n-1}=n\]

Answer 6

or you could instead of using that formula above

use undetermined coefficients way..
\[t_n-t_{n-1}=n \\ \text{ first find homoegenous solution } t_n-t_{n-1}=0 \\ \text{ Let } t_n=Cr^n \\ \text{ so } t_{n-1}=Cr^{n-1} \\ Cr^n-Cr^{n-1}=0 \\ \text{ assume } r,C \neq 0 \\ \text{ divide both sides by } Cr^n \\ 1-r^{-1}=0 \implies 1=r^{-1} \implies 1=r \\ \text{ so homogeneous solution is } t_n=C (1)^n \text{ or just } t_n=C\]

now time to guess the particular solution
my guess is that it will be linear and I'm basing this off of the right hand expression which is n
But we only need to really look at An instead of An+B since we already have a constant as a part of our solution (see homogeneous solution)

\[t_n-t_{n-1}=n \\ \text{ Let } t_n=A n \\ t_{n-1}=A(n-1) \\ \text{ plug \in } \\ An-A(n-1)=n \\ \text{ distribute } \\ An-An+A=n \\ \text{ so } t_n=An \text{ fails } \\ \text{ \let's try } t_n=An^2+Bn \\ t_{n-1}=A(n-1)^2+B(n-1) \\ An^2+Bn-A(n-1)^2-B(n-1)=n \\ An^2+Bn-An^2+2An-A-Bn+B=0 \\ 2An+(-A+B)=n \\ \implies -A+B=0 ; 2A=1 \\ A=\frac{1}{2} \\ B=\frac{1}{2} \\ \\ \]

so the final solution should include both homogeneous and particular solution
\[t_n=\frac{1}{2}n^2+\frac{1}{2}n+C\]

Answer 7

you can also use generating function

Answer 8

Thanks for all the information covering a bunch of different methods. The method I need to use appears to be:

Find characteristic equation (homogeneous part):

tn - 2t(n-1) = 0
n - 2 = 0
n = 2

Find general solution for non homogeneous part:

Form of (n - b)^(d +1) where d is the degree of polynomial and b is from the part of the equation that I mentioned earlier that is said to have to be in the form x^n. So if it was 4^n, b = 4. However with n^2, I'm unsure what b value this takes or if I have to convert it to x^n somehow.

Say b = 4 and d = 1 for this example, then

(n - 4)^2

so the 2 parts combined =

(n-2)(n-4)^2

so n = 2 n = 4 and n =4

So after finding the roots then I need to finish the question by solving for the constant coefficients.

Answer 9

Roots would then be used as

tn = c1(2^n) + c2(4^n) + c3(4^n)

Answer 10

Classic sonic*


c:


@rebeccaxhawaii


@mathmale

@Directrix


@ShadowLegendX

@jim_thompson5910

1: I fear that I can't help with this one; sonnnniiikkkkku.... (>:D), however, those whom I named should help.

2: Isn't this chemistry?

Answer 11

It's for an algorithms class. Thanks though!

Answer 12

:) gotta go fast ;)

Answer 13

let me read your response real quick

Answer 14

so you only looking at one type of form for a particular solution is what I see from your post above

Answer 15

that form being:
\[t_n=(n - b)^{d +1}\]

Answer 16

@MissSmartiez You're too slow!

Answer 17

tn=(n−b)d+1 + homogeneous part.

Homogeneous part of that example was (n - 2)

Answer 18

so homogeneous + non homogeneous

Answer 19

we need to compare this to the right hand side of the equation which is n^2

so that would mean we would want to choose
\[t_n=(n-b)^{2+1}=(n-b)^3\]
hmmm....

\[t_{n-1}=(n-1-b)^3=(n-b-1)^3=(n-b)^3-3(n-b)^2+3(n-b)-1 \\ \text{ so you have } t_n-2t_{n-1}=n^2 \\ \\ \text{ plug in } \\ (n-b)^3-2[(n-b)^3-3(n-b)^2+3(n-b)-1]=n^2 \\ -(n-b)^3+6(n-b)^2-6(n-b)+2=n^2 \\ \]


this form doesn't seem to be working...

Answer 20

it looks like you are trying to do this by guessing the particular solution though
so I might choose to go with
\[t_n=An^2+Bn+C\]

Answer 21

since the right hand side is n^2

Answer 22

if the right hand side side was n^3
I would write a 3rd degree polynomial with 4 unknown constant values

Answer 23

http://web.cs.wpi.edu/~cs504/s00m/notes/recurrence/solve/step2/step2.html
i love this website
when I was learning what guess I should choose for the particular solution

Answer 24

hey @Its_Sonic I think I might have figured out the way you are trying to do

Answer 25

\[t_n-2 t_{n-1}=1^n n^2\]
is a way you can express your equation
this means b=1 and d=2

Answer 26

\[(n-2)(n-1)^3 =0 \text{ this is our new characteristic equation }\]

Answer 27

the (n-2) came from the homogeneous part
and the (n-1)^3 came from the right hand side of the equation which will give us our particular solution

Answer 28

\[t_n=c_1 2^n+c_2 1^n+c_2 x 1^n+c_3 x^2 1^n \\ \text{ or we can write as } \\ t_n=c_1 2^n +c_2+c_2x+c_3 x^2\]

Answer 29

tell me what you think when you want

Answer 30

Ahhh that actually makes sense to me now. The right side is in form b^n . p(n) but I kept seeing only b^n in examples without the polynomial part. Because it was missing entirely I didn't think n^2 was just the p(n) portion.

Answer 31

I never seen this way
so sorry for slowness

Answer 32

What strategy would be best to solve for the constants? Notes use Gaussian elimination for one.

Answer 33

I usually plug in the initial conditions and solve any resulting system of equations
and yes Gaussian elimination is a method
it is probably much better that the more elementary ways that I normally use :p

so basically I don't have a better method of offer you :(
but that doesn't mean one doesn't exist