# Proving finite-automata transition function for string concatenation

I'm having a few problems with this proof and I'm not sure where to start.

In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple

$$M = (Q,\Sigma,\delta, q_0, F)$$

Where $Q$ is a set of states, $\Sigma$ is a set of symbols, $\delta$ is a transition function between states, $q_0$ is the starting state, and $F$ is a set of accepting states for the DFA.

The problem in my assignment is as follows:

A DFA is given with a transition function $\delta$ , which is a function from $$Q * \Sigma \to Q$$ We extend the domain of the defi nition of $$ \hat\delta : Q * \sideset{}{^*}\Sigma \to Q$$ That is for every pair $<q,s>$, where $q \in Q$ and $s$ is any string of symbols over $\Sigma$, the extended function value $$\hat\delta (q, s) \in Q$$ is defi ned as follows: $$\hat\delta (q, \varepsilon ) = q$$ and $$\hat\delta (q, xa) = \delta ( \hat\delta (q, x), a)$$ The de finition intends to capture the notion of a DFA starting with any state $q$, and after reading a string $s$, reaches state $\hat\delta (q, s)$

Prove by induction on the length of the string that for all $q \in Q$ and all strings $x$ and $y$,

$$\hat\delta (q, xy) = \hat\delta ( \hat\delta (q, x), y)$$ where $xy$ is the concatenation of $x$ and $y$.

My current problem is that I don't know where to start induction. It says to perform induction on the length of the string but it isn't clear to start on string $x$ or string $y$. Also, I am bad at induction.

Choose any string $x \in \Sigma^*$ and let $y \in \Sigma^n$ have length $n \geq 0$. We proceed by induction on $n \geq 0$.
Base Case: For $n = 0$, we have that $y = \varepsilon$. (Fill in the rest here.)
Induction Step: Assume that the claim holds for $n' = n - 1$, where $n \geq 1$. It remains to show that it holds for $n' = n$. Indeed, let $y = za$, where $z \in \Sigma^{n - 1}$ has length $n - 1$ and $a \in \Sigma$ has length $1$. Then it follows that: \begin{align*} \hat\delta(\hat\delta(q, x), y) &= \hat\delta(\hat\delta(q, x), za) \\ &= \delta(\hat\delta(\hat\delta(q, x), z), a) \\ &= \cdots \text{fill the rest in here} \cdots \\ &= \hat\delta(q, xza) \\ &= \hat\delta(q, xy) \end{align*}