It is obviosly $\frac{N(N-1)}{2}$. For any (k,k+1) we have Fibonaccy tipe sequence with $a_{0}=k,a_{1}=k+1,k\ge 1$. In this sequence has not another terms with $a_{i+1}=a_{i}+1,a_{i}\ge 1$. It proved needed result.

Here's the solution: Let those two consecutive terms be $a_{1},a_{2}$. we have: $a_{2}-a_{1}\le 0$, so $a_{2}\le a_{1}$ $a_{2}+a_{1}>N$, so $a_{1}+a+2\ge N+1$ All we have t do is count the number of pairs $(a_{1},a_{2})$. Case 1: $N$ is even. Because $a_{1}\ge a_{1}$ and $a_{2}+a_{1}\ge N+1$, obtain $2a_{1}\ge N+1$, so $a_{1}\ge \frac{N}{2}+1$. So, we can write $a_{1}=\frac{N}{2}+k$, where $k$ is a positive integer, $k\le \frac{N}{2}$, because $a_{1}\le N$. We can also write $a_{2}=\frac{N}{2}+p$, $p$ is an integer, such that $-\frac{N}{2}+1\le p\le \frac{N}{2}$, $p\le k$, because $a_{1}\ge a_{2}$, $0<a_{2}\le N$. We have $k\ge p$ and $k+p\ge 0$. Then for every value of $k$, $1\le k\le \frac{N}{2}$, there are $2k$ values of $p$, therefore the total number of $(p,k)$ (which is equal to the number of $(a_{1},a_{2})$), is: $\sum_{i=1}^{\frac{N}{2}}(2i)=(\frac{N}{2})(\frac{N}{2}+1)$ Case 2: $N$ is odd. Because $a_{1}\ge a_{1}$ and $a_{2}+a_{1}\ge N+1$, obtain $2a_{1}\ge N+1$, so $a_{1}\ge \frac{N+1}{2}$. So, we can write $a_{1}=\frac{N-1}{2}+k$, where $k$ is a positive integer, $k\le \frac{N+1}{2}$, because $a_{1}\le N$. We can also write $a_{2}=\frac{N-1}{2}+p$, $p$ is an integer, such that $-\frac{N-1}{2}+1\le p\le \frac{N+1}{2}$, $p\le k$, because $a_{1}\ge a_{2}$, $0<a_{2}\le N$. We have $k\ge p$ and $k+p\ge 0$. Then for every value of $k$, $1\le k\le \frac{N+1}{2}$, there are $2k-1$ values of $p$, therefore the total number of $(p,k)$ (which is equal to the number of $(a_{1},a_{2})$), is: $\sum_{i=1}^{\frac{N+1}{2}}(2i-1)=(\frac{N}{2}+1)^{2}$ So the answer is $(\frac{N}{2}+1)^{2}$ if $N$ is odd and $(\frac{N}{2})(\frac{N}{2}+1)$ if $N$ is even.

the correct answer is $\frac{N(N+1)}{2}$...

maky wrote: the correct answer is $\frac{N(N+1)}{2}$... We construct a bijection from the set $F$ of all fibonacci sequences with the given properties to the set $M : = \{(a,b) \in \mathbb{N}^{2}: 0<b \le a \le N\}$. Clearly $M$ has $\frac{N(N+1)}{2}$ elements, so we are done. First let $a_{n}$ be a sequence in $F$. By assumption there are two consecutive positive terms $a_{n}$ and $a_{n+1}$, and we easily see $a_{k}>0$ for $k \ge n$. On the other hand by the explicit formula for fib. sequences there has to be some $k$ s.t. $a_{k}\le 0$. By shifting of indices we therefore get a unique normal form of the fib. sequence, which is characterized by : $a_{0}\le 0$, $a_{k}>0$ for all $k \ge 1$. By induction it can easily be seen that for every fib. sequence in normal form we have: (a) For $k \le-1$ at least one of $a_{k}$ and $a_{k+1}$ is $\le 0$. (b) For $k \ge 3$ we have $a_{k}\ge a_{1}+a_{2}$. We conclude that a fib. sequence in normal form is in $F$ iff $a_{1},a_{2}\le N$. (c) Now the rest is easy: The bijection $f: F \to M$ is given by $f((a_{n})_{n}) : = (a_{1},a_{2})$, where $(a_{n})_{n}$ is the unique normal form of the fib. sequence. This is well defined as $0 < a_{1},a_{2}\le N$ by (c) and $0 \ge a_{0}= a_{2}-a_{1}$ which implies $a_{2}\le a_{1}$. Injectivity and surjectivy are clear by construction.

that is the official solution, too. good job, solyaris ! the solution i gave in the contest was somewhat different. i defined the relation $\sim$ between elements of $\mathbb{Z}^{2}$. two pairs of integers are similar if they generate the same fibonacci sequence. it is very easy to see that $\sim$ is an equivalence relation, and now we are interested in the number of classes with at least one representant with both components in $[1,N]$. we try to find a recurrence : (denote by $x_{k}$ the number of classes with at least one representant with both components in $[1,k]$) $x_{1}=1$, that is $(1,1)$. $x_{2}=3$, that is $(1,1)\sim(1,2)$, $(2,1)$, $(2,2)$. then when we go from $n$ to $n+1$ we get that the pairs $(i,n+1)$ with $1\leq i\leq n$ are similar to ones already counted (with both components in $[1,n]$), and pairs $(n+1,i)$ with $1\leq i\leq n+1$ form new classes. thus $x_{n+1}=x_{n}+n+1$ and we are done. i missed a lot of details but this is the main idea

maky wrote: the correct answer is $\frac{N(N+1)}{2}$... I do not quite understand. Take $N=3$, you have $4$ pairs: $(3,3),(3,2),(3,1),(2,2)$. By "two consecutive terms" does the problem mean exactly two terms or at least two terms?

for $N=3$ there are also $(2,1)$ and $(1,1)$. for any sequence that is requiered, we know that it has two consecutive terms both in the interval $[1,N]$. the sequences are the same if they differ by shifting of indices.

Sorry, I misunderstood the problem. i thought there ar eexactly two terms in the range. Then here's my solution: Look at the two consecutive terms $a_{1},a_{2}$ such that $a_{1}+a_{2}>N$, $a_{1},a_{2}\le N$. Therefore $a_{1}+a_{2}$ is in the range $[N+1,2N]$; for $a_{1}+a_{2}=N+k$, there are $(N-k)+1$ values for $a_{1}$, because $a_{1},a_{2}$ are integers that belong to $[1,N]$. Also, every value of $a_{1}$ yields a distinct value of $a_{2}$ if the sum $a_{1}+a_{2}$ is given. Threfore the total number of sequences which is the total number of pairs $(a_{1},a_{2})$(because evry distinct sequence has a distinct pair $(a_{1},a_{2})$) is: $\sum_{i=1}^{N}(N-k)+1=N^{2}-\frac{N(N+1)}{2}+N=\frac{N(N+1)}{2}$