Inducting on the sum of products of terms of a sequence Heres a nice problem that I've been working on for a while and it's statement is as follows:

Suppose $n$ is a positive integer. We let $\mathcal{F}$ to be the set of positive integer sequences of the form $a_1 = 1$ and $a_{i+1} \leq a_i + 1$ for $1 \leq i \leq n-1$. Find $\sum_\mathcal{F} (a_1 a_2 \cdots a_n)$.

Here's what I have so far; I've divided it into four paragraphs for it to look nice stylistically, so I had to use 4 "Reveal spoilers", apologies on that part.

 For $n=j$, denote the desired sum as $f(j)$. I claim that the answer is $f(n)=(2n-1)!!$. We will prove this by induction with the base case $n=3$, with the lower cases manually checked; suppose now that this result holds for $n=k$; we now prove that it holds for $n=k+1$.


 There are three cases to examine: the first case holds when the sequence begins with $1,1,\ldots$, the second one holds if the sequence begins with $1,2,\ldots$ with the third digit less than $3$, whereas the third case holds if the sequence begins with $1,2,3,\ldots$.


 1. For this case, it suffices to take all the sequences for the case $n=k$ and insert the digit $1$ between the pre-existing first and second digits. (for instance, when inducting from $n=3$ to $n=4$, we would take the set of sequences $\{111,112,121,122,123\}$ and change them into $\{1111,1112,1121,1122,1123\}$) Its not hard to check that this generates all such sequences that satisfy the first case.


2. Similarly to the first case, we take all sequences for the case $n=k$ and insert the digit $2$ between the pre-existing first and second digits. (for instance, when inducting from $n=3$ to $n=4$, we would take the set of sequences $\{111,112,121,122,123\}$ and change them into $\{1211,1212,1221,1222,1223\}$) Its not hard to check that this generates all such sequences that satisfy the second case.

Anybody have an idea on how to complete the proof (ie. complete case 3 and wrap the entire induction by calculating that from the hypothesis $n=k$, it follows that for $n=k+1$, $f(n)=(2k+1)!!$? What I believe we should do is take all sequences of the form 123... (for $n\ge 3$) and append digits to the end, but I'm not quite sure now how to complete this argument. A solution for case 3 would be appreciated, and have a good day.
 A: The induction that you'd want to do is on the last digit, since that gives you full control over what the digit you can append is, thereby avoiding the issue that you're facing.
Specifically, let $ T(n,k)$ be the sum of the product of sequences of length $n$ that end with the digit $k$. It satisfies the recurrence
$$ T(n+1, k) = k \times \sum_{i=k-1}^n T(n,i). \quad \quad (1) $$
This is equivalent to
$$ \frac{ T(n+1, k) } { k } - \frac{ T (n+1, k-1)} { k-1} = T(n,k-2). \quad \quad (2) $$
Here are some initial values. Each row corresponds to a value of $n$, in increasing $k$.
1
1, 2
3, 6, 6
15, 30, 36, 24
105, 210, 270, 240, 120
(Full disclosure: I used OEIS to find the expression for the individual terms. Otherwise, you can stare at it and guess the form, since each term looks like some multiple of the term above it. E.g. We can see that $T(n,1) = (2n-3)!!$ )
We can verify that $ T(n,k) = \frac{ k (2n-k-1)!}{2^{n-k} (n-k)!}$ satisfies the recurrence and initial starting values.
Note: It's easier to work with recurrence relation (2), since it avoids the summation on terms that don't seem to be easily factorable. IE
$$ \frac{ T(n+1, k) } { k } = \frac{ T (n+1, k-1)} { k-1} + T(n,k-2) = \ldots $$
From there, we can show that $ f(n) = \sum_{k=1}^n T(n,k) = T(n+1,1) = \frac{ (2n)!}{ 2^n n!} = (2n-1)!!$
