Proving a Recurrence Relation

Question

can someone help me understand this? Let $n ≥ 1$, and let $C_n$ be the number of integer sequences $c_1, . . . , c_n$ of length $n$ such that $1 ≤ c_1 ≤ c_2 ≤ · · · ≤ c_n$ and $c_i ≤ i$ for each $i$. $C_0=1$. Prove that that $C_n$ satisfies the recurrence relation $$C_n = C_0C_{n−1} + C_1C_{n−2} + · · · + C_{n−1}C_0$$ I don't really understand what $C_n$ is by the original definition. Thank you!

Answer 1

I'm going to invent a term here, which is "climbing sequence". A climbing sequence of length $n$ is a sequence of $n$ positive integers such that each number is at least as large as the previous one, but is no larger than its position in the sequence. In other words, it is a sequence $c_1, \ldots, c_n$ such that $1 \leq c_1 \leq \ldots \leq c_n$ and $c_i \leq i$.

What does a climbing sequence look like? Well, $1, 2, 3$ is a climbing sequence of length 3 because $1 \leq 2 \leq 3$, and $1 \leq 1$, $2 \leq 2$, $3 \leq 3$. But $1, 1, 1$ is also a climbing sequence of length 3, because $1 \leq 1 \leq 1$ and $1 \leq 1$, $1 \leq 2$, $1 \leq 3$. However, $1, 2, 4$ is not a climbing sequence, because the 3rd term is bigger than 3. And $1, 3, 2$ is not a climbing sequence, because the 3rd term is smaller than the 2nd one.

In fact, here are all the climbing sequences of length 3:

$1, 1, 1$
$1, 1, 2$
$1, 1, 3$
$1, 2, 2$
$1, 2, 3$

So there are 5 such sequences. In your problem, $C_n$ is the number of climbing sequences of length n, so $C_3 = 5$.