Ordered Sum of Odd Numbers

Question

EDIT: The vectors can be any length. That is $k$ is not fixed.

For a given natural number $n$, let $S_1(n)$ be the number of vectors $(a_1, a_2, \ldots, a_k)$ such that

$$a_1 + a_2 + \cdots + a_k = n$$

where each $a_i$ is an odd natural number. What is the value of $S_1(n)$? Is there a closed form solution?

A Variation

Suppose we relax the condition on vectors so that all $a_i$ must be odd except $a_1$ and $a_k$, which can be either even or odd. Call the number of such vectors $S_2(n)$. What is the value of $S_2(n)$? Is there a closed form solution?

Notes

This question was inspired by a recent post by phoenix, where we are asked a question about vectors. I have figured out some bounds for $SO$ in that post. In particular, it is between $\sqrt{2^{n - 1}}$ and $2^{n - 1}$. Note that $2^{n - 1}$ is the number of vectors adding to $n$ without the odd restriction.

Answer 1

Let $a_n$ be the number of compositions of $n$ into odd parts. Note that $a_1=a_2=1$. Because the last entry in the sum is $1$ or $3$ or $5$ and so on, the $a_i$ satisfy the recurrence $$a_{n+1}=a_n+a_{n-2}+a_{n-4}+\cdots.$$

This recurrence is also satisfied by the Fibonacci numbers. For from $b_{i+1}=b_i +b_{i-1}$ we obtain $b_{n+1}=b_n+b_{n-1}=b_n+b_{n-2}+b_{n-3}=b_n+b_{n-2}+b_{n-4}+b_{n-5}$ and so on.

Same recurrence, same initial conditions: The sequence $(a_n)$ is the Fibonacci sequence. Fibonacci counts again!

Remark: For the sake of full disclosure, I should mention that I first computed the $a_k$ up to $k=6$ and only found the simple argument after that.

Answer 2

The number of ways to write $n$ as a sum of $k$ odd numbers is trivially given by the coefficient of $x^n$ in: $$ \left(x+x^3+x^5+\ldots\right)^k = \left(\frac{x}{1-x^2}\right)^k $$ so it equals the number of ways to write $n-k$ as a sum of $k$ even numbers, that is: $$ \left\{\begin{array}{rcl}0 & \text{if} & n-k\equiv 1\pmod{2}, \\ \binom{\frac{n-k}{2}+k-1}{k-1} & \text{if} & n-k\equiv 0\pmod{2},\end{array}\right. $$ since: $$ \frac{1}{(1-x)^k}=\sum_{m\geq 0}\binom{m+k-1}{k-1}x^m.$$

Answer 3

If $a_j$ is an odd natural number, then there exists a nonnegative integer $b_j$ such that $a_j = 2j + 1$. Hence, if $a_1 + a_2 + \cdots + a_k = n$ then substitution yields \begin{align*} 2b_1 + 1 + 2b_2 + 1 + \cdots + 2b_k + 1 & = n\\ 2b_1 + 2b_2 + \cdots + 2b_k & = n - k\\ b_1 + b_2 + \cdots + b_k & = \frac{n - k}{2} \tag{1} \end{align*} Equation 1 is an equation in the nonnegative integers. The number of solutions is the number of ways we can insert $k - 1$ addition signs in a row of $(n - k)/2$ ones, which is $$\binom{\frac{n - k}{2} + k - 1}{k - 1}$$