Alice sends binary messages to Bob. Every message must end in 1, and the number bits equal to 1 in the message, including the last, cannot exceed a certain $k$ limit. For $n, k ∈ Z> 0$, let $M (n, k)$ be the number of messages of exactly n length, with a maximum of $k$ equal bits to 1, that Alice can send a Bob. Examples: $M (n, 1) = 1$ for all $n$; $M (2, 3) = 2$; $M (3, 3) = 4$; $M (5, 3) = 11$ etc.
Closed form:
I know every message ends with 1 so its n-1.
Also i know too $M(n,1) = 1$ for any n.
$M(n,1)$ = n^(k-1)
After that i am a bit confuse what i should do next, if someone could help me.
You have a binary message of length $n$, so a vector of 0 and 1 which has length $n$ and the last entry has to be a $1$. Hence, you only have to consider messages of length $n-1$ with the additional constraint that they may at most contain $k-1$ times a $1$.
Imagine a chain of length $n-1$. Then the number of way to redistribute $l$ ones an $n-1-l$ zeros on the chain is simply given by $\binom{n-1}{l}$. Now, we want to have all messages containing $1,...,k$ ones. Therefore, we sum $\sum_{l=0}^{k-1}\binom{n-1}{l}$ since one $1$ is fixed in the last bit and, therefore, $M(n,k)=\sum_{l=0}^{k-1}\binom{n-1}{l}$.