The sequence $\left(a_{n}\right)_{n\in\mathbb{N}}$ is defined recursively as $a_{0}=a_{1}=1$, $a_{n+2}=5a_{n+1}-a_{n}-1$, $\forall n\in\mathbb{N}$ Prove that $$a_{n}\mid a_{n+1}^{2}+a_{n+1}+1$$for any $n\in\mathbb{N}$
Problem
Source: Moldova TST 2018
Tags: number theory
WolfusA
05.03.2018 23:29
Prove by induction that $a_n\cdot a_{n+2}=a_{n+1}^{2}+a_{n+1}+1$
ArqadyFan_1337
05.03.2018 23:33
WolfusA wrote: Prove by induction that $a_n\cdot a_{n+2}=a_{n+1}^{2}+a_{n+1}+1$ how much did it take you to observe that "rule"? Didn't look so easy for me, but it actually is Thanks!
WolfusA
05.03.2018 23:39
The easy level of solution understanding doesn't make the question easy and vice versa. You use this tactic: $a_{n}\mid a_{n+1}^{2}+a_{n+1}+1\implies a_{n+1}^{2}+a_{n+1}+1=ka_n$ for some $k\in Z$. Just check for two values of $n$, that $k$ isn't a constant. So try to find it in recursion of $a_n$
ArqadyFan_1337
05.03.2018 23:46
WolfusA wrote: The easy level of solution understanding doesn't make the question easy and vice versa. You use this tactic: $a_{n}\mid a_{n+1}^{2}+a_{n+1}+1\implies a_{n+1}^{2}+a_{n+1}+1=ka_n$ for some $k\in Z$. Just check for two values of $n$, that $k$ isn't a constant. So true to find it in recursion of $a_n$ well explained, thank you.