Let $a_1, a_2, \ldots$ be a sequence which is not eventually periodic, i.e. there do not exist constants $K$ and $N$ such that $a_m = a_{m+K}$ for all $m \geq N$. Prove that the number of distinct subsequences $a_{t+1},\ldots,a_{t+k}$ of length $k$ (here $t$ runs through the positive integers) is at least $k+1$.
My thought was to do induction, with $k=1$ being clear (if the number is $1$, then the sequence is constant). If the number of sequences of length $k$ is $s_k$, then clearly $s_{k+1} \geq s_k$, so assuming $s_k \geq k+1$ as hypothesis and supposing for contradiction that $s_{k+1} \leq k+1$, we force $s_k = s_{k+1} = k+1$. But how to continue?
Any help appreciated!