MathDB

In the real axis, there is bug standing at coordinate

x=1

. Each step, from the position

x=a

, the bug can jump to either

x=a+2

x=\frac{a}{2}

. Show that there are precisely

F_{n+4}-(n+4)

positions (including the initial position) that the bug can jump to by at most

n

steps.
Recall that

F_n

is the

n^{th}

element of the Fibonacci sequence, defined by

F_0=F_1=1

F_{n+1}=F_n+F_{n-1}

for all

n\geq 1

Problem Statement