Fibonacci Numbers 
I am supposed to solve these questions, I started when number 10 , in a traditional way , I computed the number  of different hopscotch games when we have 5 squares , and I got 8 ways, when we have 6 squares  I got 12 ways , and when we have 7 squares  I got 20 ways , but i could not find a formula , and in fact i did not know if i considered the all options , 
Any hint ? 
Thanks in advance? 
 A: This is the dominos and monominos problem.  Here, I will use $\!~^\bullet_\bullet$'s to represent the "both feet at the same time" and $\bullet$ to denote a single foot at a time.
To prove combinatorially why this winds up being recursive of the form $G_{n} = G_{n-1}+G_{n-2}$, note that for a hopscotch game with a total of $n$ dots, $\underbrace{\underline{~}\underline{~}\underline{~}\underline{~}\cdots\underline{~}}_{n~\text{dots}}$ exactly one of two things will happen.
$$\textbf{First case}~~~~~~~~~~~~~~\underbrace{\!~_\bullet^\bullet\underline{~}\underline{~}\underline{~}\underline{~}\cdots\underline{~}}_{n~\text{dots}}$$
$$\textbf{Second case}~~~~~~~~~\underbrace{\bullet\underline{~}\underline{~}\underline{~}\underline{~}\cdots\underline{~}}_{n~\text{dots}}$$
In the first case with a double dot on the far left, note that it will be:
$$\textbf{First case}~~~~~~~~~~~~~~\underbrace{\!~_\bullet^\bullet}_{2~\text{dots}}\underbrace{\underline{~}\underline{~}\underline{~}\underline{~}\cdots\underline{~}}_{n-2~\text{dots}}$$
$$\textbf{Second case}~~~~~~~~~~~~~~\underbrace{\bullet}_{1~\text{dots}}\underbrace{\underline{~}\underline{~}\underline{~}\underline{~}\cdots\underline{~}}_{n-1~\text{dots}}$$
By addition principles of counting, the total number of ways of having $n$ dots will be the number of ways of being in the first case plus the number of ways of being in the second case (since they form a disjoint partition of the ways of doing it for $n$ dots).
The number of ways of being in the first case will be the number of ways of arranging the $n-2$ remaining dots into either single or double scotches (i.e. $\bullet$'s and $\!~^\bullet_\bullet$'s), which by our definition is the number we call $G_{n-2}$
Similarly, the number of ways in the second case will be the number $G_{n-1}$
Hence $G_n = G_{n-1}+G_{n-2}$
Now, note that $G_1 = 1$ since to have one dot can only be accomplished as $\bullet$, and that $G_2 = 2$ since to have two dots can be accomplished as either $\bullet \bullet$ or as $\!~_\bullet^\bullet$.
We get then the sequence: $1,2,3,5,8,13,21,34,\dots$, which should be recognized as exactly the Fibonacci sequence (if we append $G_0=1$ at the beginning)

For the follow up question, note that we can break these hopscotch games with $n$ squares into cases.  There will be a total of either $0,1,2,\dots,\lfloor\frac{n}{2}\rfloor$ double scotches.  Let the number of double scotches be called $k$.  How many "jumps" do the children make with $k$ double scotches and $n$ total squares?  How many such hop scotch boards exist with $k$ double scotches and $n$ total squares?
Summing over all values of $k$ gives the desired result.
A: I felt the need for a little more detailed answer:
Let $S_n$ denote the number of those hopscotch games which end with one single square. Let $D_n$ denote those hopscotch game that end with a double square. The total number of hopscotch games consisting of $n$ squares is then $$G_n=S_n+D_n.$$
Obviously $$S_1=1 \text{ and } D_1=0$$ and $$S_{n+1}=D_n+S_n$$ and $$D_{n+1}=S_n.$$
So, $G_n$ is almost a Fibonacci sequence: 
$S_1=1, D_1=0, G_1=1$; $S_2=S_1+D_1=1$, $D_2=S_1=1$, $G_2=2$; $S_3=S_2+D_2=2$, $D_3=S_2=1$, $G_3=3.$ So, $$G_3=G_2+G_1.$$ 
In general
$$G_{n+1}=S_{n+1}+D_{n+1}=D_n+S_n+S_n=G_n+D_{n-1}+S_{n-1}=G_n+G_{n-1}.$$
The relationship between the Fibonacci  numbers $F_n$ and the hopscotch numbers ($G_n$) is simple:
$$F_0=0, F_1=1, F_2=G_1, F_3=G_2, \cdots, F_n=G_{n-1}, \cdots$$
The other way to count the number of hopscotch games consisting of $n$ squares is as follows. Let $k$ denote the number of double squares in the game of $n$ squares. For $k$ we have all the integers from $0$ to $2k\le n$. For a $k$ $2k$ squares will be used to create double squares and the remaining $n-2k$ squares will be used as single squares. That is, we have $n-2k+k=n-k$ places and we have to choose $k$ of them for the double squares. As a total we have 
$$F_{n+1}=G_n=\sum_{k=0}^{2k\le n}{n-k \choose k}$$ possibilities to create hopscotch games. At the same time the relationship between the Fibonacci numbers and the number of the hopscotch games is given.
For the Fibonacci numbers we have then
$$F_{n}=\sum_{k=0}^{2k\le n-1}{n-1-k \choose k}.$$
