Derek (no school given) offered the following insights into this problem: - and nicely explained too - thank you Derek.

From observation, we compile the table below:

n-row pyramid	Ways to count 1-2-3-...
1	1
2	3
3	7
4	15
...	...

The pattern can be deduced by considering route backwards, i.e. from n back to 1. The general n-row pyramid is shown below:

Starting at the orange square, we assert that there are 0 routes leading to the final square:
orange square with zero

1 step earlier, at the bright yellow squares, there is 1 route leading to the final square:

1 step earlier, at the light yellow squares, the situation becomes slightly different.The top, left and right squares all have 1 route leading to the final square. However, the middle squares have 2 routes as they each connect to 2 bright yellow squares (each of which are routes leading to the final square):
1 then 212 then 11011 in each row

1 step earlier, the top, left and right squares all have 1 route whilst the middle squares have 3 routes as they each connect to 2 light yellow squares, bearing a total of 3 routes. We repeat this reasoning and get the following pattern:
six rowed pyramid

It is clear that these are the binomial coefficients. 2 of Pascal's triangles have been arranged together and the numbers along the two slanted edges represent how many ways to count 1-2-3-...-n. For example, in the diagram of the 6-row pyramid above, we see that there are 1+5+10+10+5+1+5+10+10+5+1 = 63 ways to count 1-2-3-4-5-6.

We further notice that 1, 5, 10, 10, 5, 1 are the binomial coefficients

æ
ç
è

5
k

ö
÷
ø

,k = 1, 2, 3, ¼, 5 . We generalise by claiming that the number of ways of counting 1-2-3-...-n is twice (because there are two Pascal's triangles) the sum of all the binomial coefficients of the n-1^th row minus 1 (because of the overlapped 1 down the central column) which can be written as

n-1
å
k=0

æ
ç
è

n-1
k

ö
÷
ø

- 1.

Editor's comment: at this point it may be worth mentioniing that the sum of the binomial coefficients are powers of 2. Why?

Chen of the Chinese High School took a slightly different approach (similar to the one offered by Andrei of Tudor Vianu National College):

We shall define T(n) to be the number of ways to count 1 - n in a triangular array of 1 - n. We shall solve this problem by establishing a recurrence relation, and hence finding a formula for T(n).

When n=1, T(1)=1 and when n=2, T(2)=3. We observe that in a triangular array of 1-3, the number of ways to get to the number '2' directly above the number '3' is given by T(2) and the number of ways to get to the '2' on the left of '3' can be easily computed to be 2.

Similarly, there are 2 ways to get to the '2' on the right of the '3'.

Hence, T(3)=T(2)+2²=7 For T(4), we observe again that the number of ways to get to the '3' directly above of the '4' is given to be T(3).

Furthermore, the number of ways to get to the '3' to the left of the '4' is the sum of the number of ways to get to the '2's adjacent to the '3'.

Since by the previous result, there are 2 ways of getting to the '2', there are 2+2=4 ways of getting to the '3' to the left of the '4', and similarly for the '3' to the right of the '4'. Hence, T(4)=T(3)+2(2²)=T(3)+2³ Extending this argument to T(n), we obtain the recurrence T(n)=T(n-1)+2^(n-1).

However, since T(n-1)=T(n-2)+2^(n-2), which is also equal to T(n-3)+2^(n-3)+2^(n-2).

Thus, it is not difficult to see that T(n) = 1+2+2²+2³+...+2^(n-1) or 2ⁿ - 1

Editor's comment: The final result can be verified by summing the geometric series with first term 1 and common ratio 2. You can test your understanding of this proof using the proof sorter at http://www.nrich.maths.org/public/viewer.php?obj_id=1398.