Problems & Puzzles: Puzzles

Puzzle 439. Fibonacci Primes Puzzle Juan López González sent the following interesting puzzle: We consider the Fibonacci sequence Fib(k) 1, 1, 2, 3, 5, 8, 13,... Now we consider the sequence of primes p(Fib(k)): 2, 2, 3, 5, 11, 19, 41, 73, 139, 257, 461, 827, 1471, …  Let's exclude from the previous sequence the terms 2, 2 and 3 and let f(k) to be: 5, 11, 19, 41, 73, 139, 257, 461, 827, 1471, … If we define c(k) as the number of primes P such that f(k)<P<f(k+1), the first terms of this sequence are: 1, 2, 4, 7, 12, 20, 33, 54,  … These first members of the sequence satisfy the recursion:  c(k+2)=c(k)+c(k+1) +/- 1, k=>1. Q1. Does the recurrence holds for all  k>1?

---

Contributions came from Luis Rodríguez, Giovanni Resta, Farideh Firoozbakht.

Luis wrote:

Naturlich!!
The last sequence is simply the Fibonacci 's -1 Because the primes were taken in the same order than the Fibonaccis The difference between two Fibonaccis is precisely another Fibonacci.

***

Giovanni wrote:

The answer is Yes, the recurrence, in the form c(k+2)=c(k)+c(k+1)+1 holds for every k>=1.

The reason is simple. Basically it depends on the fact that, from the defintion of c(k) we have that c(k) = pi(f(k+1))-pi(f(k))-1, where pi(x) if the function that gives the number of primes less or equal to x. since f(k)=P(fib(k) and by definition pi(P(x))=x, we have c(k)=fib(k+1)-fib(k)-1,
thus c(k+2)=fib(k+3)-fib(k+2)-1 and c(k+1)=fib(k+2)-fib(k+1)-1.
Now fib(k+3)=fib(k+2)+fib(k+1), so c(k+2)=fib(k+2)+fib(k+1)-fib(k+2)-1 = fib(k+1)-1 and c(k)+c(k+1)= fib(k+1)-fib(k)-1 + fib(k+2)-fib(k+1)-1 = fib(k+2)-fib(k)-2= fib(k+1)-2. Hence c(k+2)=c(k)+c(k+1)-1 as requested.

***

Farideh wrote:

For all natural numbers k, c(k+2)=c(k)+c(k+1)+1 because according to
the definition of c(k) we have c(k)=Fib(k+4)-Fib(k+3)-1=Fib(k+2)-1.
Hence c(k)+c(k+1)+1=(Fib(k+2)-1)+(Fib((k+1)+2)-1)+1=Fib(k+2)+Fib(k+3)-1= Fib(k+4)-1=c(k+2).

***