# Help to prove a conjecture (recurrence)

Establishing a sequence by the following recurrence:

$C_1=1$

$C_2=3$

$C_{n+2}=C_{n+1}+C_n$

It looks like Fibonacci sequence, but we obtain very different numbers. I observed two things that I want to prove, but I couldn't figure it out.

First: If $n$ is a prime number, then $n|C_n-1$. I find this impressive because the tests that I did with the odd numbers that is not prime, $n$ does not divide $C_n$. I tested all odd numbers until $51$.

Second: if $m$ and $n$ is prime numbers, then $gcd(C_m,C_n)=1$. A corollary is that the numbers of primes is infinity. I tested until $n=71$. (this statemente in Fibonacci sequence is true)

Third: if $n$ is a prime number, then $C_n$ is only divisible by primes greater than $n$. (also, this statemente in Fibonacci sequence is true)

The problem is that some statements that is true in Fibonacci sequence are not true in this sequence, like: If $m|n$, the $F_m|F_n$. Or, $gcd(F_m,F_n)=F_{gcd(m,n)}$. This statementes are not true in this sequence. And without some tools it's hard to prove something substantial. (sorry for my english)

• We have $C_{n+2} - C_{n+1} - C_n = 0$, so we try $C_n = \lambda^n$ giving $\lambda^2 - \lambda - 1 = 0$ so that $2\lambda_{1,2} = 1 \pm \sqrt{5}.$ Hence our general solution is $C_n = A\lambda_1^n + B\lambda_2^n$, now we want to put in our initial conditions $1 = A \lambda_1 + B\lambda_2$ and $3=A\lambda_1^2 + B\lambda_2^2$. – Zain Patel Jun 7 '17 at 1:16
• I did that, but I didn't see this helping to prove those statements, – Daniel Cintra Jun 7 '17 at 1:25
• Ever heard of Lucas numbers? en.wikipedia.org/wiki/Lucas_number – Jack D'Aurizio Jun 7 '17 at 1:51
• This is relevant, too: en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test – Jack D'Aurizio Jun 7 '17 at 1:52
• This is called the Lucas sequence. Let $F_n$ be the $n$th Fibonacci number : $F_0=0, F_1=1,$ etc. Then $C_n=F_{n-1}+F_{n+1}.$ .... If $p$ is prime and $p\ne 5$ then $p$ does divide $C_{n-1}.$ But $5$ does not divide any $C_n.$ The sequence of remainders of $C_n$, modulo $5,$ is $1,3,4,2,1,3,4,2,1,3,4,....$ Also we have $C_n+C_{n+2}=5 F_{n+1}.$ – DanielWainfleet Jun 7 '17 at 5:24