(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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.

2. Relevant equations

3. 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Number of Sequences

**Physics Forums | Science Articles, Homework Help, Discussion**