For any two finite sets $X$ and $Y$, prove that $\#(Y^X)=\#(Y)^{\#(X)}$ by induction I came across the following exercise while self-studying Terrence Tao's book Analysis I:

Exercise 3.6.4 Let $X$ and $Y$ be finite sets. Then $Y^X$, the set of functions with domain $X$ and range $Y$, is finite and $\#(Y^X)=\#(Y)^{\#(X)}$.

Note: This question has been asked twice before (here and here) on this site. My attempt was a proof by induction, which was not present in either of these posts. So, I ask merely that any answers correct my inductive step, or any other errors, and not give alternate solutions. With that in mind, here is my go: 
Let $X$ and $Y$ be finite sets with bijections $f:X\to\Bbb N_n$ and $g:Y\to\Bbb N_m$ (where $\Bbb N_n$ denotes the set of natural numbers less than $n$, where I am using the convention that the natural numbers start at zero). In this proof, we fix $m$ and induct on $n$. If it happens that $n=0$, then $\#(Y^X)=1$, as there is a unique function $\emptyset\to Y$ (uniqueness is a vacuous truth, in this case). Since $m^0=1$, the claim is trivial in this case, and we may assume that $n>0$. If it happens that $n=1$, then $Y^X$ is the set of all functions $\{*\}\to Y$, as $X$ is a singleton set. Notice that if the image of $\{*\}$ under any of these maps is greater than one, the image of $x$ cannot be unique, which contradicts our assumption that $Y^X$ consists of only functions. Therefore, the image of any one of these maps is a singleton, and it suffices to count only the elemtnts of $Y$, as $\{*\}$ remains fixed: $$\#(Y^X)=\#\left(\bigcup_{y\in Y}\{y\}\right)=\#(Y)^{\#\{*\}}.$$
Furthermore, suppose our claim holds for some $n\in\Bbb N$. Then, if $x'\notin X$ and $Z=X\cup\{x'\}$, $$\begin{align}Y^Z :&=\{f\mid \operatorname{dom}(f)=Z\land \operatorname{ran}(f)=Y\} \\ &=\{(x,y)\in f\mid x\in X\cup\{x'\}\land y\in Y\} \\ &= (?) \\ &=Y^X\times Y^{\{x'\}},\end{align}$$
and hence, $$\#(Y^Z)=m^n\times m=m^{n+1}.$$
This closes induction. What am I missing in the inductive step? What should go in place of $(?)$ in the third line above? It seems only plausible that it works out to be $Y^X\times Y^{\{x'\}}$, otherwise I am not sure how to apply the inductive hypothesis. Also, one can arrive at a contradiction of the original claim, considering $$\begin{align}\#(Y^Z)&=\#\left(\{f\mid \operatorname{dom}(f)=X\land \operatorname{ran}(f)=Y\}\cup \{f\mid \operatorname{dom}(f)=\{x’\}\land \operatorname{ran}(f)=Y\}\right) \\ &= m^n+m\neq m^{n+1} \end{align}.$$
Why is this incorrect? Thanks in advance. 
Update: Combinatorially speaking, the carnality of $Y^Z$ should be $\#(Y^X)\times\#(Y)$, as one can pair $\{x'\}$ with each element of $Y$, which as we mentioned above, should yield the cardinality of $Y$. But, this is in contradiction with what I have written before, and I am still interested in why it is false. 
 A: Skimming over the OP's question and comments, I come away with the distinct impression that the only way to make this interesting is to set up the induction to give us the right perspective.
Lemma 1: Let $X$ and $Y$ be two finite sets with $\#(Y) \gt 0$ and $\bar x \notin X$. Let $\hat X = X \cup \{\bar x\}$.  The number of functions from $\hat X$ into $Y$ is given by
$\tag 1 \#(Y^X) \times \#(Y)$
Proof (hint):
Let $S = \{\bar x\}  \times Y$. Define a bijective mapping from ($Y^X \times S)$ to $Y^{\hat X}$ via
$\quad (f, (\bar x, y)) \mapsto f \cup \{(\bar x, y)\} \text{ where } f \in Y^X \text{ and } y \in Y$ $\quad \blacksquare$

Lemma 2: Let $n \in \mathbb N$. Suppose for any two finite sets $X$ and $Y$ the following is true:
$\tag 2 \text{If } \#(X) + \#(Y) = n \text{ Then } \#(Y^X)=\#(Y)^{\#(X)}$
Then if $U$ and $V$ are any two finite sets satisfying $\#(U) + \#(V) = n + 1$, then it must be true that 
$\tag 3 \#(V^U)=\#(V)^{\#(U)}$.
Proof Sketch
If $\#(U) \times \#(V) = 0$ we can easily show that equation $\text{(3)}$ holds true. So we assume that $\#(V) \gt 0$ and $U$ has at least one element $u$. Set $X = U \text{\\} \{u\}$ and $Y = V$ so that $\#(X) + \#(Y) = n$. Using the assumed truth of all the $\text{(2)}$ statements and lemma 1, we see that equation $\text{(3)}$ holds true once again. $\quad \blacksquare$
The OP can use lemma 2 in a proof by induction. They might feel more comfortable starting the inductive base case at $n = 1$ or $n = 2$. If they really love math they can really start at $n = 0$, but they would have to cry out that
$\quad \#(\emptyset^{\emptyset}) = 0^0 = 1$
That might require taking a few drinks first!

Looking over this answer and considering Cameron Buie's comments, it appears that I am using the method of infinite descent (induction by any other name).
A: You want to conclude that
$$
Y^Z = Y^{X} \times Y^{\{x'\}} 
$$
This will not be an equality of sets strictly speaking, since the first set has subets of tuples in $Z \times Y$, and the second one has subsets of tuples with each coordinate again being a tuple, in $X \times Y$ and $\{x'\} \times Y$ respectively. So I don't think you can conclude your argument by a chain of equalities. You can however do the following bijection
$$
\Gamma : Y^Z \longrightarrow Y^{X} \times Y^{\{x'\}} 
\\ f \longmapsto (f^*, f_*)
$$
with $f^*: x \in X \mapsto f(x) \in Y$ and $f_*(x') = f(x')$, whose inverse is 
$$
\Gamma^{-1} : Y^{X} \times Y^{\{x'\}}  \longrightarrow Y^Z
\\ \Gamma^{-1}(f,g)(z) = \cases{g(x') \quad \text{ if } z = x' \\ f(z) \quad \text{otherwise} }
$$
Which shows what you ultimately need, that is, that 
$$|Y^Z| = |Y^{X} \times Y^{\{x'\}}|
$$
I don't know if this is a satisfactory answer, but as far as I know, this is not an 'avoidable' step. 
Also, I think you could improve your inductive step, since the induction is on the size of the set and nothing else, I think it would be better to pick some $x' \in Z$ and define $X := Z \setminus \{x'\}$. Because in your current construction, you are adding an element to a previously defined set, which in principle you don't have. You could take it one step further and only prove this for sets of the form $\{1, \dots, n\}$ and then prove as an auxiliary result that $A^B \simeq C^D$ if $A \simeq C, B\simeq D$.
