Function from integers to integers

We need to find the number of integers $k$ such that $f(2k+1) = 2015 \implies f(k) + f(k+1)= 2015$ .

---

Claim 1: $\gcd (f(n), f(n+1)) = 1$ for all $n \in \mathbb{N}$

Proof: Use strong induction. The base cases can be manually verified. Now, suppose $n$ is even, say $n= 2k$ . Then, $f(n+1) = f(k) + f(k+1)$ and $f(n) = f(k)$ , so $\gcd (f(n), f(n+1))= \gcd (f(k), f(k+1)),$ which is equal to $1$ by the inductive hypothesis. Now suppose $n$ is odd, say $n= 2k+1$ . Then, $f(n)= f(k) + f(k+1)$ and $f(n+1) = f(k+1)$ , so $\gcd (f(n), f(n+1)) = \gcd (f(k), f(k+1))= 1$ . $\blacksquare$

---

Claim 2: For all integers $a$ and $b$ such that $\gcd (a, b)= 1$ , there exists a unique $n$ such that $f(n) = a, f(n+1)= b$ .

Proof: Use strong double induction on $a$ and $b$ . For the base case $(a, b)= (1, 1)$ , note that if $t$ is an odd integer $>1$ , for all $k$ , $f(2^k t) = f(t) = f((t-1)/2) + f((t+1)/2)>1$ , so $f(n)=1$ if and only if $n$ is a power of $2$ , and the only consecutive powers of $2$ are $2^0$ and $2^1$ .

Suppose the claim holds true for all $1 \leq a \leq i$ and $b=1$ . Suppose $m$ is the unique integer such that $f(m) = a, f(m+1)= 1$ . Then, note that $f(2m+1) = a+1, f(2m+2)= 1$ . Again, if there existed another integer $t$ such that $f(t) = a+1, f(t+1) = 1$ , then we would have $f(t-1)/2) = f(t) - f(t+1) = a$ (note that since $t+1$ must be a power of $2$ , $t$ is odd), so the uniqueness of $m$ implies $\dfrac{t-1}{2} = m \implies t= 2m+1$ , so $2m+1$ is the unique integer such that $f(2m+1) = a+1, f(2m+2) = 1$ . Thus, our claim holds true for all integers $a$ when $b=1$ .

For some $a$ , let $m$ be the unique integer such that $f(m) = a, f(m+1) = b$ . Then, by the mimicking the logic, as in the first paragraph $2m$ is the unique integer such that $f(2m) = a, f(2m+1) = a+b$ and $2m+1$ is the unique integer such that $f(2m+1)= a+b, f(2m+2) = b$ . Note that $\gcd (a, a+b) = \gcd (a, b) = 1$ . Thus, if the claim us true for a pair $(a, b)$ where $\gcd (a, b) =1$ , it must also be true for the pairs $(a, a+b)$ and $(a+b, a)$ .

Consider any co prime pair $(p, q)$ .If $q>p$ , by our inductive hypothesis, the claim is true for $(p, q-p)$ , and hence, must also be true for $(p, q-p+p) = (p, q)$ . We similarly prove the case when $p>q$ . $\blacksquare$

---

By the claims, the answer is simply the number of integers $a, b$ such that $a+b= 2015$ and $\gcd (a, b) = 1$ . Since $\gcd (a, b) = \gcd (a, a+b) = \gcd (a, 2015)$ , this is simply the number of integers $<2015$ and coprime to $2015$ , which is simply $\varphi (2015) = \boxed{1440}$ .