For $n \ge 2$ the terms in the sequence
$a = \{1, 6, 17, 45, 118, 309, \ldots\}$ are related by the difference equation
$$a_{n+2} = \boxed{\phantom{XX}} \, a_{n+1} + \boxed{\phantom{XX}} \, a_n $$
The values are positive or negative integers.
Can anyone help me with the equation please. appreciated
On
HINT: A quick eyeball estimate says that each term is very roughly three times the previous term, so do a little arithmetic:
$$\begin{array}{rcc} n:&0&1&2&3&4&5\\ a_n:&1&6&17&45&118&309\\ 3a_{n-1}:&-&-&18&51&135&354\\ a_n-3a_{n-1}:&-&-&?&?&?&? \end{array}$$
Added: There are of course mechanical solutions, but it’s also useful to be able to spot patterns.
On
$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $a_{n + 2} = xa_{n + 1} + ya_{n}$. $$ \!\!\!\!{\cal F}\pars{x,y} \equiv \half\bracks{% \pars{x + 6y - 17}^{2} + \pars{6x + 17y - 45}^{2} + \pars{17x + 45y - 118}^{2} +\pars{45x + 118y - 309}^{2}} $$ Minimize ${\cal F}\pars{x,y}$ respect $x$ and $y$. If the minimum of ${\cal F}\pars{x,y}$ is $\large\tt zero$, then the values of $x$ and $y$ you found are the right ones $\pars{~\mbox{it assumes}\ x\ \mbox{and}\ y\ \mbox{are}\ n-\mbox{independents}~}$.
That procedure yields the global minimum ${\cal F}\pars{x, y} = 0$ at $\color{#0000ff}{\large x = -1,\quad y = 3}$.
Then $$\color{#0000ff}{\large% a_{n + 2} = -a_{n + 1} + 3a_{n}} $$
Hint: Our recurrence relation is of the form $a_{n+2} = x a_{n+1} + y a_n$, and we would like to determine $x$ and $y$. For $n=1$, we get the equation $17 = 6x+y$, and for $n=2$, we get $45 = 17x+6y$. We now solve this linear system.