Solve the following for \(a_n\) given that \(a_0=0\) and \(a_1=1\)

\(a_n=a_{n-1}+2a_{n-2}+n\)

\(a_n=a_{n-1}+2a_{n-2}+n^2\)

\(a_n=2a_{n-1}-a_{n-2}+n^2\)

\(a_n=a_{n-1}+2a_{n-2}+2^n\)

\(a_n=a_{n-1}a_{n-2}\) (with initial conditions \(a_0=1\) and \(a_1=2\))

\(a_n^2=a_{n-1}a_{n-2}\) (with initial conditions \(a_0=1\) and \(a_1=2\))

\(a_n=na_{n-1}+a_{n-2}\)

\(a_n=a_{n-1}^2+a_{n-2}\)

\(a_n=a_{n-1}^2+a_{n-2}^2\)

## Comments

Sort by:

TopNewestFor numbers 1-3, the trick is to use the characteristic equation to solve. First, eliminate all terms that are not in the form of \(ia_j\):

\[\begin{align*}a_n&=a_{n-1}+2a_{n-2}+n\\a_{n-1}=a_{n-2}+2a_{n-3}+(n-1)\end{align*}\]

Subtracting the two, we get

\[a_n-a_{n-1}=a_{n-1}+a_{n-2}-2a_{n-3}+1\]

But there's still a \(1\) in there! Do it again!

\[\begin{align*}a_n-a_{n-1}=a_{n-1}+a_{n-2}-2a_{n-3}+1\\ a_{n-1}-a_{n-2}=a_{n-2}+a_{n-3}-2a_{n-4}+1\end{align*}\]

Subtract:

\[\begin{align*}a_n-2a_{n-1}+a_{n-2}=a_{n-1}-3a_{n-3}+2a_{n-4}\\a_n-3a_{n-1}+a_{n-2}+3a_{n-3}-2a_{n-4}=0\end{align*}\]

Finally, we have it in the form we want. Now, we'll use the characteristic equation, which is an equation that looks like this:

\[x^4-3x^3+x^2+3x-2=0\]

Basically, it takes its coefficients from the recurrence relation. Solving, we get \(x=-1,1,1,2\). From generating functions, we can now say that

\[a_n=c_1\cdot(-1)^n+(c_2+c_3n)\cdot1^n+c_4\cdot2^n\]

What we did here was take the roots of the equation and use their exponentials to develop the relation. For repeated roots, we have to create an entire polynomial with an ascending degree: if the root \(x_0\) is repeated \(k\) times, it'll be \((c_0+c_1n+c_2n^2+\dots+c_kn^{k-1})x_0^n\). Lastly, we solve for \(c_1,c_2,c_3,c_4\) using a system of equations. Note that since there are four constants, we need to know four terms of the sequence, so we must compute \(a_2=3\) and \(a_3=8\). Solve the system of equations

\[\begin{cases}0=c_1\cdot(-1)^0+(c_2+c_3\cdot0)\cdot1^0+c_4\cdot2^0\\1=c_1\cdot(-1)^1+(c_2+c_3\cdot1)\cdot1^1+c_4\cdot2^0\\3=c_1\cdot(-1)^2+(c_2+c_3\cdot2)\cdot1^2+c_4\cdot2^2\\8=c_1\cdot(-1)^3+(c_2+c_3\cdot3)\cdot1^3+c_4\cdot2^3\end{cases}\]

Eventually, we get \((c_1,c_2,c_3,c_4)=\left(-\frac1{12},-\frac54,-\frac12,\frac43\right)\), so

\[a_n=-\frac1{12}\cdot(-1)^n-\frac54-\frac{n}2+\frac43\cdot2^n\]

That technique takes care of 1-3. It also takes care of 5 as you can let \(a_n=2^{b_n}\) with \(b_0=0\) and \(b_1=1\) such that \(b_n=b_{n-1}+b_{n-2}\), the famous Fibonacci sequence. Similarly, 6 has \(a_n=2^{b_n}\), \(b_0=0\), \(b_1=1\), and \(2b_n=b_{n-1}+b_{n-2}\). – Cody Johnson · 2 years, 9 months ago

Log in to reply

Given thing \(a_n=a_{n-1}+2a_{n-2}+2^n\)

Next recurrence \(a_{n-1}=a_{n-2}+2a_{n-3}+2^{n-1}\)

JUST MULTIPLY THIS BY 2 ON BOTH SIDES\(2a_{n-1}=2a_{n-2}+4a_{n-3}+2^n\)

Now subtract from given !!!!

You get \(a_n-3a_{n-1}+4a_{n-3}=0\)

comparable to \(x^3-3x^2+4=0\)

Has roots \(x=-1,2,2\)

And then we get \(a_n=c_1(-1)^n+(c_2+nc_3)2^n\)

Solve to get \(c_1=\frac{1}{9}\) , \(c_2=\frac{-1}{9}\) . \(c_3=\frac{2}{3}\)

And then \(a_n=\dfrac{1}{9}(-1)^n-\dfrac{2^n}{9}+\dfrac{2}{3} n2^n \) – Aditya Raut · 2 years, 8 months ago

Log in to reply

– Happy Melodies · 2 years, 6 months ago

Wow, nice thought @Aditya Raut :)Log in to reply

– Cody Johnson · 2 years, 8 months ago

Very good!Log in to reply

– Aditya Raut · 2 years, 9 months ago

Thank you very very much Cody !!! Now please try for last three questions ...I found no way to solve them :(Log in to reply

– Finn Hulse · 2 years, 7 months ago

Wow, that's insane. :PLog in to reply

– Happy Melodies · 2 years, 9 months ago

There is a typo at line 7: should be \(a_n\) instead of \(a_{n-2}\).Log in to reply

Try with generating functions. – Alessio Di Lorenzo · 2 years, 9 months ago

Log in to reply

Solve \(a_{n}\) in terms of function of n only with initial values \(a_{0}=0, a_{1}=1, a_{n}=a_{n-1}^2 + a_{n-2}^2 \)

Here we observe one inequality. As series is growing,

\(a_{n} => a_{n-1}\) It implies

\(a_{n-1}^2+ a_{n-2}^2 <= 2a_{n-1}^2 \)

i.e.\( 2a_{n+1}^2<=a_{n} <= 2a_{n-1}^2\)

Observe \(a_{n}=2a_{n-1}^2\) is a series whose solution is

\(a_{n}=2^2^n\)

Hence we conclude that our solution will be of the same type

\(a_{n}=f^2^n\)

where f is a real number less than 2 (and definitely greater than zero.) Now all our efforts are to find f which satisfies above equation. As I worked out for calculating f,I came to know that it is irrational number and its value depends upon value of

\(a_{0},a_{1},a_{2},a_{3}...\)

For exact expression for f see this ,

" www.fq.math.ca/Scanned/11-4/aho-a.pdf "

Value of f up to fourteen significant digit is 1.11148222558297....

Another thing to point here is that \(a_{n}\)=nearest integer to \(f^2^n\)

as value may be floating we have to take into account only integer values.

This is analytic solution but is correct for first 8th term.....For other terms more accurate value of f is needed otherwise it is perfect solution. Below is the verification of my solution...As i had said more significant digits are required for correctness.

\( n\) \( a_{n} \) \( f^2^n\)

– Aamir Faisal Ansari · 2 years, 9 months agoLog in to reply

– Aamir Faisal Ansari · 2 years, 9 months ago

Haa...one thing.....Not applicable for n=0 caseLog in to reply

The questions 7 to 9 are extremely tricky ..... No method worked :( – Aditya Raut · 2 years, 9 months ago

Log in to reply

– Happy Melodies · 2 years, 4 months ago

I don't think the method of characteristics equation will work here... Instead, multiply the RHS (\(a_n\)) and LHS by \(x^n\), then sum the terms with respect to \(n\). Then, look for power series and simplify the expression,Log in to reply

– Happy Melodies · 2 years, 4 months ago

Hmm Qn 7 is hard... (Refer to this link)[http://www.math.upenn.edu/~wilf/gfology2.pdf]. I think can still multiply by \(x^n\) on both sides then take sum. Differentiate the \(n(a_{n-1})\) term (with summation) then solve differential eqn.... Haven't worked that out but I think it might work. If you have no idea what I am talking about, the link above is a good guide to Generating Functions, which is very useful in solving recurrence type problems.Log in to reply

– Ronak Agarwal · 2 years, 4 months ago

I have worked that out the differential equation and it turns out to be unsolvable. The differential equaiton turns out to be \(x^{ 2 }f^{ ' }\left( x \right)+({ x }^{ 2 }+x-1)f(x)+x=0\) where \(\\ f(x)=\sum _{ n=0 }^{ \infty }{ { a }_{ n }{ x }^{ n } } \)Log in to reply

– Happy Melodies · 2 years, 4 months ago

Hmm i am not familiar with differential equation ... (Just started learning calculus) anyone can help?Log in to reply

– Finn Hulse · 2 years, 4 months ago

If you want to learn, I learned from Khan Academy. But if you want help in explaining this to Ronak, I'm afraid I can't help.Log in to reply

– Happy Melodies · 2 years, 4 months ago

Alright I will maybe after my examsLog in to reply

@Happy Melodies what are the terms LBS and RHS? – Mardokay Mosazghi · 2 years, 4 months ago

Log in to reply

– Happy Melodies · 2 years, 4 months ago

Right Hand Side (of equation) for RHS and Left Hand Side for LHSLog in to reply

Anyone knows how to solve Q2? I'm stuck with the characteristic equation method as well as generating funcs method... – Happy Melodies · 2 years, 9 months ago

Log in to reply

given thing is \(a_n=a_{n-1}+2a_{n-2}+n^2\)

Do for \(a_{n-1}=a_{n-2}+2a_{n-3}+(n-1)^2\)

Which is \(a_{n-1}=a_{n-2}+2a_{n-3}+n^2-2n+1\).....(i)

Subtract this from Given one......... you will get \(a_{n}=2a_{n-1}+a_{n-2}-2a_{n-3}+2n-1\).........(ii)

Now write the next recurrence............. \(a_{n-1}=2a_{n-2}+a_{n-3}-2a_{n-4}+2(n-1)-1\)

\(a_{n-1}=2a_{n-2}+a_{n-3}-2a_{n-4}+2n-3\)................(iii)

Subtract (iii) from (ii) to get

\(a_{n}=3a_{n-1}-a_{n-2}-3a_{n-3}+2a_{n-4}+2\)

But we got "2" here ...... Eliminate it from again one more recurrence !!!!!!!! \(a_{n-1}=3a_{n-2}-a_{n-3}-3a_{n-4}+2a_{n-5}+2\)

Subtracting, you get \(a_n=3a_{n-1}-4a_{n-2}-2a_{n-3}+5a_{n-4}-2a_{n-5}\)

And now we find characteristic equation

\(x^5-4x^4+4x^3+2x^2-5x+2=0\)

Has it's roots \(x=-1,1,1,1,2\)

Next things you can find in Cody's solution :) – Aditya Raut · 2 years, 8 months ago

Log in to reply

– Alessio Di Lorenzo · 2 years, 9 months ago

What's q2?Log in to reply

– Happy Melodies · 2 years, 9 months ago

As in the above point 2? Solving for \(a_n\)Log in to reply

See i guess that n cannot take values 0 & 1 but when you start with n=2 and go on till 3 or 4 then you will start getting values now the difference of 2 consecutive terms will start forming an A.P. or G.P. that can be solved by method of differences,see if this works!!! – Nitish Sharma · 2 years, 9 months ago

Log in to reply