Find all possible to ways to reach a point $N$ meters away using steps that are of lengths 1 meter or 2 meters.

Question

Find all possible to ways to reach a point $N$ meters away in only 2 possible steps that are of 1 meter and 2 meter respectively.

Now let me illustrate using an example: Let the point be 4 meters away. So all possible ways to reach the point:

1. (1,1,1,1)
2. (2,2)
3. (1,2,1)
4. (2,1,1)
5. (1,1,2)

My approach:

I sought to the computational power of my laptop, I brute forced to reach the solution.

Yet this isn't really a solution, I am looking for some more logically derived solution. Any help is appreciated.

Answer 1

Let $a_n$ be the number of ways of reaching a point $n$ meters away by taking steps of $1~\text{m}$ or $2~\text{m}$. There is only one way to move $1~\text{m}$ (take a $1~\text{m}$ step), and two ways to move $2~\text{m}$ (take two $1~\text{m}$ steps or one $2~\text{m}$ step). Hence, we have the initial conditions \begin{align*} a_1 & = 1\\ a_2 & = 2 \end{align*} An admissible sequence of steps that results in moving $n$ meters must begin with a $1~\text{m}$ step or a $2~\text{m}$ step. If it begins with a $1~\text{m}$ step, then it must be followed by an admissible sequence of steps that results in moving $(n - 1)~\text{m}$, of which there are $a_{n - 1}$. If it begins with a $2~\text{m}$ step, then it must be followed by an admissible sequence of steps that results in moving $(n - 2)~\text{m}$, of which there are $a_{n - 2}$. Hence, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2}$$ The first few terms of the sequence are $1, 1, 2, 3, 5, 8, 13, 21, 34, 55$, so this is the Fibonacci sequence.

Answer 2

In Mathematica this function is called IntegerPartitions:

So:

IntegerPartitions[5, 4, {1, 2}]

means: give all partitions of the number $N=5$ consisting of up to 4 "steps" (in your terms) of size $1$ and $2$ without respect to order. The output is:

(*

{{2, 2, 1}, {2, 1, 1, 1}}

*)

It is then a simple matter to get the three distinguishable orders of the first set of "paths" and the four distinguishable orders of the second set of "paths."