Recurrence Relations (need help)

For 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{aligned}a_n&=a_{n-1}+2a_{n-2}+n\\a_{n-1}=a_{n-2}+2a_{n-3}+(n-1)\end{aligned}$

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{aligned}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{aligned}$

Subtract:

$\begin{aligned}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{aligned}$

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}$.

Try with generating functions.

The questions 7 to 9 are extremely tricky ..... No method worked :(

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

 0                                  0                                             1
 1                                  1                                             1.2353
 2                                  1                                             1.5261
 3                                  2                                             2.3292
 4                                  5                                             5.4255
 5                                29                                            29.4361
 6                              866                                            866.485
 7                        750797                                           750797.4995
 8          563696885165                                            563696885249

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!!!

Anyone knows how to solve Q2? I'm stuck with the characteristic equation method as well as generating funcs method...