I know that the rank (i.e. minimal number of generators) of the product $\mathbb{Z}\times F_2$, of the infinite cyclic and free group on two generators, is three, but the only argument I could quickly piece together uses quite advanced tools (name-bearing and quite recent results on deficiency of a group/presentation). Can anyone point me to a direct, elementary proof, if there is one? Presumably, this (i.e. that the rank is the sum of ranks) also holds for product of a free group of finite rank and any cyclic group/product of cyclic groups?
Rank of a free group times a free abelian group.
combinatorial-group-theoryfree-abelian-groupfree-groupsgroup-theory
Related Solutions
The point is that given a free group $G$, you can always choose different system of free generators (just like you can choose different bases for a vector space). In linear algebra any vector space is free, but when we define the dimension, we have to make sure that all bases have the same number of elements.
Here it's the same: for instance, if $G$ is free on $\{a,b\}$, it is also free on $\{a,ab\}$, or on $\{ab,aba\}$. Now all those sets have the same number of elements (and the theorem precisely says that they have to), but there is no reason why it should be true at first sight.
Especially since non-commutative free groups are complicated and can have weird behavior: for instance, a free group on $n$ generators can have a free subgroup on $m$ generators with $m>n$ (actually, a free group of rank $2$ has free subgroups of any finite rank, and even of infinite countable rank).
Now as a comment pointed out, the idea of the proof is to reduce to a case we already know: the case of abelian groups, where it is much easier to see that a free abelian group (so a free $\mathbb{Z}$-module) has a well-defined rank, ie any system of free generators has the same length. It turns out that a system of free generators of a free group given after abelianization a system of free generators of the corresponding free abelian group, so they all have the same size.
As has been noted in the comments, there is some linear algebra going on under the hood. That is maybe a hint that we should view this problem geometrically. To that end, I'll be calling elements of this group "vectors", and thinking of them as living in some integer lattice of $\mathbb{R}^n$. Indeed, these kinds of questions arise very naturally in the geometry of numbers.
We say a set of vectors $\{v_1, \ldots, v_i \}$ is primitive exactly when it can be extended to a basis of the lattice. So in this problem we are interested in knowing when $\{ w \}$ is primitive.
If we write $w = g_1^{n_1} g_2^{n_2} \cdots g_k^{n_k}$ in terms of the "natural" basis $\{ g_1, \ldots, g_k \}$, there turns out to be a nice combinatorial description of primitivity:
$w = g_1^{n_1} g_2^{n_2} \cdots g_k^{n_k}$ is primitive if and only if $\text{gcd}(n_1, \ldots, n_k) = 1$.
A nice computational proof can be found as Theorem $2.1$ in Magliveras, van Trung, and Wei's "Primitive Sets in a Lattice" (see here).
This turns out to be related to the comment about finding a matrix whose determinant is $\pm 1$. Indeed, the proof in the above article works by cleverly using bezout's lemma to take a (row) vector $w = (n_1, \ldots, n_k)$ and find $k-1$ new (row) vectors $v_2, \ldots, v_k$ so that when we assemble these vectors into a matrix, we find
$$ \text{det} \begin{pmatrix} - w - \\ - v_2 - \\ \vdots \\ - v_k -\end{pmatrix} = \text{gcd}(n_1, \ldots, n_k) $$
When $\text{gcd}(n_1, \ldots, n_k) = 1$ this matrix has determinant $1$, and thus is invertible as an integer matrix. But this is exactly what it means for your rows to be a basis. The linked article is nice because it shows you what the other basis elements are too.
I hope this helps ^_^
Best Answer
Let $G=\mathbb{Z}^n\times F_m$ where $F_m$ denotes the free group of rank $m$. Consider the abelianization of $G$, i.e., the surjective map $$ \pi:G\twoheadrightarrow G/[G,G]\simeq\mathbb{Z}^{n+m}. $$ Since this map is surjective, if $\{g_1,\dots,g_k\}$ generate $G$, then $\pi(g_1),\dots,\pi(g_k)$ generate $\mathbb{Z}^{n+m}$. Since the rank of $\mathbb{Z}^{n+m}$ is $n+m$, this implies that $k\geq n+m$.
On the other hand, we can write down a generating set of $G$ consisting of $n+m$ generators as follows: $\mathbb{Z}^n$ is generated by $n$ coordinate vectors $\{e_1,\dots,e_n\}$ and $F_m$ is, by definition, generated by $m$ elements $\{f_1,\dots,f_m\}$. Therefore, $G$ is generated by $\{e_1,\dots,e_n,f_1,\dots,f_m\}$.
Since we have shown that it is possible to generate $G$ with $n+m$ generators and, in addition, that any generating set for $G$ must have at least $n+m$ elements, it follows that exactly $n+m$ generators is the best possible, i.e., the rank is $n+m$.
For the further generalization, combining this argument with the fundamental theorem of finitely generated abelian groups should provide exactly what you're looking for.