- #1

sylar

- 11

- 0

## Homework Statement

In how many ways can we form a sequence of non-negative integers a_1,a_2,...,a_(k+1) such that the difference between the successive terms is 1 (any of them can be bigger) and a_1 =0.

## Homework Equations

## The Attempt at a Solution

For k=1, there is only one way: 01. For k=2, there are two ways: 012 or 010. For k=3, there are three ways: 0121,0123 or 0101. For k=4 there are six ways: 01210,01212,01232,01234,01010 or 01012. Note that when k is even, the number of such sequences is twice the number of such sequences when we have k-1 because when k is odd, there is no possibility for the sequence to finish with 0, and so we can add both of the two possible choices to the end of the sequence. But i couldn't find a nice formula relating the case k is odd to the one k is even? Can you help me with this?

Note: There are 10 ways for k=5, 20 ways for k=6 and 35 ways for k=7.