First, note that the sequence is non-decreasing. Also, $a_{i+1} - a_i$ must be either $0$ or $1$, and it depends on whether $a_{i+1+k} - a_{i+k} = 0$ or $1$. Define $b_i = a_{i+1} - a_i$, then the condition means that $b_{i+k} = b_i$, and so each residue class mod $k$ has a constant value of $b_i$. Since this is the only constraint, there are $2^k$ ways to choose this. If the sequence of $b_i$ is determined, $a_1$ is also uniquely determined (it is the number of $1$'s among the first $k$ $b_i$ + 1), so there are overall exactly $2^k$ sequences. $\blacksquare$

Rewrite as $f$. Obviously $f(n)\le f(n+1)\le f(n)+1$. Note that if $f(n+1)=f(n)$ then $f(n+1+k)=f(n+k)$, while if $f(n+1)=f(n)+1$ then $f(n+1+k)=f(n+k)$. Hence the function is determined by $f(1),f(2),\cdots f(k+1)$ alone. Conversely, if there are $f(1)$ distinct elements amongst them, and $f(i)\le f(i+1)\le f(i)+1$ for all $1\le i\le k$, then we can construct such a function. Suppose $f(1)=t$, then we need $t$ "+1"s between adjacent numbers in $f(1)$ to $f(k+1)$. There are $\binom{k}{t}$ ways to do this. Summing over all $t$, this gives $2^k$.

Here is a solution written with every possible motivation I had. Also, I just totally loved this problem! The answer if $f(k)=2^k$. Note that $a_n\le a_{n+1}\le a_n+1$ as we are just adding one more term into the previous set which is either a new term, or one of the pre-existing ones. Now note that $a_i$ is the number of distinct elements in\[a_1,a_2,\ldots,a_{k+i}\]and that $a_{i+1}$ is the number of distinct elements in\[a_1,a_2,\ldots,a_{k+i},a_{k+i+1}.\]So if $a_{i+1}=a_i$, then both the sequences have the same number of distinct elements, which means $a_{k+i+1}\in\left\{a_1,a_2,\ldots,a_{k+i}\right\}$. Now using the fact that $a_{k+i+1}in{a_{k+i},a_{k+i}+1}$ we get that this forces $a_{k+i+1}=a_{k+i}$. Similarly, if $a_{i+1}=a_i+1$, then we can get $a_{k+i+1}=a_{k+i}+1$. Now let $+$ denote the operation $a_i\rightarrow a_{i+1}$ when $a_{i+1}=a_i+1$ and $\square$ denote the operation $a_i\rightarrow a_{i+1}$ when $a_{i+1}=a_i$. Due to what we derived above, we get that the operation of $a_{k+i}\rightarrow a_{k+i+1}$ is same as that of the operation $a_i\rightarrow a_{i+1}$. This gives us that if we determine the order of operations on the sequence $\left\{a_1,a_2,\ldots, a_{k+1}\right\}$, then we automatically get the order of operations on the entire sequence which is described as below. \begin{align*} a_1&\rightarrow a_2\rightarrow\cdots\rightarrow a_{k+1}\\ a_{k+1}&\rightarrow a_{k+2}\rightarrow\cdots\rightarrow a_{2k+1} .\end{align*} So we just need to determine the sequence $\left\{a_1,a_2,\ldots, a_{k+1}\right\}$. Let there be $m$ many $+$ operations, and thus $k-m$ many $\square$ operations in the sequence of first $k+1$ numbers; where $0\le m\le k$. So we get that there are $m+1$ distinct elements in the sequence. But we also had that this value equals $a_1$, and so $a_1=m+1$. Thus after picking the ordering of the $+$ and the $\square$ operations, we get the sequence from $a_1$ to $a_{k+1}$, which on extending further gives us our entire sequence. Now to finish, we have can select a value for $m$ from $0\le m\le k$, and then, we will have $\binom{k}{m}$ ways to choose the positions of the $+$, which sets the position for the rest of the $\square$ operations too. So we get that our final answer is $f(k)=\displaystyle\sum_{m=0}^k \binom{k}{m}=2^k$ and we are done.

Wow! Neat bijection. I guess Im getting good C practice before RMO The answer is $2^k$. First note that $a_i$ is a non-decreasing sequence due to it's definition. So, $a_{i+1}-a_i=0,1$ if $a_{k+i+1}-a_{k+i}=0,1$ and so if we define $d_i=a_{i+1}-a_i$, then $d_i$ is periodic with period $k$. Now what matters is the choice of $d_1,\hdots , d_k$, which can be chosen in $2^k$ ways, so we are done. Remark. Many times, what is important with such problems which create strong 'dependencies' is to utilize those 'dependencies' and identify uniquely determined objects. The problem then would be very easy.

We claim that there are exactly $2^k$ such sequences for any $k$. Claim: For any positive integer $n$, we have $a_{n+k+1}-a_{n+k}=a_{n+1}-a_n$. Proof. By definition, we have $0\leq a_{n+1}-a_n\leq 1$. Note that if $a_{n+k+1}=a_{n+k}$ then $a_{n+1}=a_n$, and if $a_{n+k+1}\ne a_{n+k}$, then their difference is 1, but then $a_{n+1}-a_n=1$. So, $a_{n+k+1}-a_{n+k}=a_{n+1}-a_n$. $\blacksquare$ A simple induction gives $a_{n+tk+1}-a_{n+tk}=a_{n+1}-a_n$ for any $t$. So, we really just need to ensure that $a_1$ is the number of distinct elements in the set $\{a_1,a_2,\ldots,a_{1+k}\}$. In this set, call a number $1\leq i\leq k$ good if $a_{i+1}=a_i+1$ and bad otherwise. We have that $a_1=1+\#(\text{good numbers between }1\text{ and }k\text{ inclusive})$. This can be done very easily, let there be $g$ good numbers from $1,2,\ldots,k$. Then, $a_1=1+g$ and choose $g$ good numbers in $\binom{n}{g}$ ways. Hence, \[\#(k-\text{pop sequences})=\sum_{g=0}^{k}\binom kg=2^k,\]as claimed.

Note that $a_{i+1} - a_i \in \{0, 1 \} \forall i$. Further, any $k$-pop sequence must satisfy $a_{i+1} = a_i \iff a_{i+k+1} = a_{i+k}$. And conversely, all sequences satisfying this and the fact that $a_1 = |\{a_1, \dots, a_{k+1}\}|$ work. So now we choose $a_{i+1} - a_i$ for $i = 1, 2, \dots, k$ out of $\{0, 1\}$ to get a working $k$-pop sequence. Since there are $2^k$ ways to do this, the final answer is in fact $\boxed{2^k}$. EDIT: WAIT POST #700 LESGOOOOOOOO

This is a really nice problem Claim 1: $a_i \leq a_{i + 1} \leq a_i + 1$ Observe that $a_i$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}\}$, while $a_{i + 1}$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}, a_{k + i + 1}\}$. Note that $a_{k + i + 1}$ can either add one distinct element or the number of distinct elements remain the same, so our claim is proved. Claim 2: The sequence is dependent on the selection of $\{a_1, \dots, a_{k + 1}\}$. Again, $a_i$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}\}$, while $a_{i + 1}$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}, a_{k + i + 1}$. If $a_{i + 1} = a_i$, then $a_{k + i + 1}$ must not add any distinct element, or $a_{k + i + 1} = a_{k + i}$. If $a_{i + 1} = a_i + 1$, then $a_{k + i + 1}$ must add a distinct element, or $a_{k + i + 1} = a_{k + i} + 1$. This proves our claim. To finish, note that for each $a_j$ where $j \leq k$, we can either choose $a_{j + 1} = a_j$ or $a_{j + 1} = a_j + 1$, and $a_1$ is merely the number of pairs $(a_i, a_{i + 1}) + 1$, where $a_{i + 1} = a_i + 1$. So there will be $2^k$ selections (dependent on $a_1$) for $(a_1, a_2, \dots, a_{k + 1}$, which means there are $2^k$ sequences.