How many sets $(A_1,A_2,\cdots, A_k)$ which are subsets of $\{1,2,\cdots ,n\}$ For given natural numbers $n,k$, how many are there $k$-tuples $(A_1,A_2,\cdots ,A_k)$ such that
$$A_1\subseteq A_2\subseteq\cdots \subseteq A_k\subseteq \{1,2,3,\cdots ,n\}$$
I've thought to prove by induction on $k$ that the number of $k$-tuples is equal to
$$\sum_{t=0}^n{n\choose t}k^t=(k+1)^n$$
Though I have no idea what happens when you add another subset,my idea was when I add another subset to let it be $A_1$ and shift every other subset index by $1$.Then split it into $n+1$ cases such that $|A_2|=t$ for each $t$ from $0$ to $n$.
Maybe there is a better way.
 A: The easiest solution is certainly the one in the comments, but we can approach the problem using induction in the following way:
The first observation is that the only important property of the set $\lbrace 1, 2, \dots, n \rbrace$ in the problem is that it has $n$ elements. We would have the same answer if we replaced it with any other set with $n$ elements.
We now use induction on $k$. For the base case, we consider $k = 1$. If we only want a single subset
$$ A_1 \subseteq \lbrace 1, 2, \dots, n \rbrace $$
then $A_1$ can be any of the $2^n = {(1+1)}^n$ subsets of $\lbrace 1, 2, \dots, n \rbrace$, and so the number of subsets in this case is indeed ${(k+1)}^n$.
Now suppose that the result is true for some $k$ and for every $n$. We wish to then prove that the number of ways of choosing sets $A_1, A_2, \dots, A_{k+1}$ such that
$$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_{k+1} \subseteq \lbrace 1, 2, \dots, n \rbrace $$
is equal to ${(k+2)}^n$.
We count the number of ways of choosing the subsets by considering the number of elements in $A_{k+1}$. Let this number be $m$. Then there are $\binom{n}{m}$ ways to choose the elements in $A_{k+1}$.
Now $A_{k+1}$ is a set with $m$ elements, so by our earlier observation that the set $\lbrace 1, 2, \dots, n \rbrace$ is arbitrary, we can see that once we have chosen $A_{k+1}$, the number of ways of choosing sets $A_1, A_2, \dots, A_k$ such that
$$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_k \subseteq A_{k+1} $$
is equal to ${(k+1)}^m$.
Thus the number of ways of choosing sets $A_1, A_2, \dots, A_{k+1}$ such that 
$$ A_1 \subseteq A_2 \subseteq \dots \subseteq A_{k+1} \subseteq \lbrace 1, 2, \dots, n \rbrace $$
and such that $A_{k+1}$ has $m$ elements is equal to
$$ \binom{n}{m} {(k+1)}^m. $$
We see that the total number of ways of choosing the sets $A_1, A_2, \dots, A_{k+1}$ is then equal to
$$ \sum_{m=0}^{n} \binom{n}{m} {(k+1)}^m $$
which by the binomial theorem is equal to ${(k+2)}^n$.
