Find maximum number of strings.

Question

Given a Finite Automata with fix number of input symbols $k$. What is the maximum number of strings of maximum length $n$ it can accept.

How to think about the problem and progress in the right direction?

Answer 1

If you are constructing a string of length exactly $n_0$ with $k$ distinct symbols which may each be used multiple times, then on place $1$ in the string you have $k$ choices. As each symbol is useable multiple times, you have $k$ choices also for place 2 in the string, and so on. Thus you have $k^{n_0}$ number of strings of size $n_0$. Now to get the strings of $max$ length, you have to sum all of the possible lengths $n_0$.

$\Sigma_{i=0}^n k^i$

Which is a geometric sum.