Show using induction that $\mathbb{N}^p$ is countable for any $p \in \mathbb{N}$ For $p \in \mathbb{N}$, define $\mathbb{N}^p$:= $\mathbb{N}\times...\times \mathbb{N}$ (p times) to be the set of p-tuples
of natural numbers.
I'm supposed to prove by induction, but I am not sure how to continue.
To prove that $\mathbb{N}^p$ is countable for any $p \in \mathbb{N}$. Let $p(n) = \mathbb{N}^n$ be the statement that $\mathbb{N}^n$ is countable for all $n \in \mathbb{N}$. First, we establish the base case $n=1$. $p(1)=\mathbb{N}^1 = \mathbb{N}$ is the set of natural number which is countable. Therefore, we establish the induction hypthesis where $n=k$ and $p(k) = \mathbb{N}^k$ is countable.  Then we proceed to prove that the statement is true for the case $n=k+1$, that $\mathbb{N}^{k+1}$ is countable. $p(k+1)=\mathbb{N}^{k+1}=\mathbb{N}^k \cdot \mathbb{N}$.
I am not sure if I can end by saying that since by hypothesis $\mathbb{N}^k$ and $\mathbb{N}$ are countable, so is $\mathbb{N}^k \cdot \mathbb{N}$.

If you know that the cartesian product of countable sets is countable, then the inductive hypothesis gives you $\mathbb N^k\times \mathbb N=\mathbb N^{k+1}$ is countable. We can also prove this formally:
Let $A=\{a_1,a_2,...\}$ and $B=\{b_1,b_2,...\}$ be countable. Then we define an injective function $f:A\times B\rightarrow \mathbb N$ by $f(a_i,b_j)=2^i3^j$. This is injective by the uniqueness of the prime decomposition, proving $A\times B$ is finite.
A non-inductive proof could look like this:
Let $p_1,p_2,...,p_k$ be distinct prime numbers. Then define the injective function $f:\mathbb N^k\rightarrow \mathbb N$ by $$f(x_1,x_2,...,x_k)=p_1^{x_1}p_2^{x_2}...p_k^{x_k}$$
Thus, $\mathbb N^k$ is countable.
