I was struggled with this question. Hopefully, @Saad helped me answer it. Luckily, I've just figured my own proof :). I hope that someone can verify it for me. Thank you so much for your help!
Let $(X_n)_{n \in \mathbb N}$ be a discrete-time Markov chain whose state space $V$ is finite. Suppose
$\psi, \phi$ are functions from $V$ to $\mathbb R_+$.
$E$ is an open subset of $V$.
$\mathbb{E}_{x} := \mathbb{E} [ \cdot | X_0 = x]$ and $\mathbb{P}_{x} := \mathbb{P} [ \cdot | X_0 = x]$.
We define $(\tau, u)$ by
$$\begin{cases} \tau &= \min \{k \in \mathbb N \mid X_k \in E \} \\ u (x) &= \mathbb E_x \left [\phi (X_{\tau}) \prod_{i=0}^{\tau-1} \psi(X_i) \right] \end{cases}$$
with the usual convention that the empty product is $1$.
Theorem: $$\left \{\begin{aligned} \forall x \in E: u(x) &= \phi(x) & (1) \\ \forall x \in E^c: u(x) &= \psi(x) \sum_{y \in V} p_{x y} u (y) & (2)\end{aligned} \right.$$ where $p_{xy} = \mathbb P_x [X_1 = y]$.
My attempt:
We first verify $(1)$. Notice that conditional on $X_0 = x$, we have $x \in E$ implies $\tau = 0$. By convention, $\prod_{i=0}^{-1} \psi(X_i) = 1$, so $u (x) = \mathbb E_x [\phi (X_0)] = \mathbb E_x [\phi (x)] = \phi (x)$. Next we verify $(2)$. For $x \in E^c$, we have
$$\begin{aligned} u (x) &= \mathbb E_x \left [\phi (X_{\tau}) \prod_{i=0}^{\tau-1} \psi(X_i) \right] \\ &= \sum _{k=0}^\infty \mathbb E_x \left [ \mathbf{1} {\{ \tau = k \}} \phi (X_{k}) \prod_{i=0}^{k-1} \psi(X_i) \right] \\ &\overset{(3)}{=} \sum _{k=1}^\infty \mathbb E_x \left [ \mathbf{1} {\{ \tau = k \}} \phi (X_{k}) \prod_{i=0}^{k-1} \psi(X_i) \right] \\ &\overset{(4)}{=} \psi(x) \sum _{k=1}^\infty \sum_{(x_1, \ldots,x_k) \in V^{k}} \mathbb E_x \left [ \mathbf{1} \left \{ \begin{aligned} \tau &= k \\ X_i &= x_i, i = \overline{1,k} \end{aligned} \right\} \phi (x_k) \prod_{i=1}^{k-1} \psi(x_i) \right] \\ &= \psi(x) \sum _{k=1}^\infty \sum_{(x_1, \ldots,x_k) \in V^{k}} \phi (x_k) \mathbb P_x \left [ \begin{aligned} \tau &= k \\ X_i &= x_i, i = \overline{1,k} \end{aligned} \right] \prod_{i=1}^{k-1} \psi(x_i) \\ &= \psi(x) \sum _{k=1}^\infty \sum_{(x_1, \ldots,x_k) \in V^{k}} \phi (x_k) \mathbb P_x \left [ \begin{aligned} \tau &= k \\ X_i &= x_i, i = \overline{2,k} \end{aligned} \;\middle|\; X_1 = x_1\right] \mathbb P_x [X_1 = x_1] \prod_{i=1}^{k-1} \psi(x_i) \\ &\overset{(5)}{=} \psi(x) \sum _{k=1}^\infty \sum_{(x_1, \ldots, x_k) \in V^{k} } \phi (x_k) \mathbb P_{x_1} \left [ \begin{aligned} \tau &= k-1 \\ X_i &= x_{i+1}, i = \overline{1,k-1} \end{aligned} \right] p_{xx_1} \prod_{i=1}^{k-1} \psi(x_i) \\ &\overset{(6)}{=} \psi(x) \sum _{k=0}^\infty \sum_{(x_1, \ldots, x_{k+1}) \in V^{k+1} } \phi (x_{k+1}) \mathbb P_{x_1} \left [ \begin{aligned} \tau &= k \\ X_i &= x_{i+1}, i = \overline{1,k} \end{aligned} \right] p_{xx_1} \prod_{i=1}^{k} \psi(x_i) \\ &\overset{(7)}{=} \psi(x) \sum _{k=0}^\infty \sum_{(x_0, \ldots, x_{k}) \in V^{k+1} } \phi (x_{k}) \mathbb P_{x_0} \left [ \begin{aligned} \tau &= k \\ X_i &= x_{i}, i = \overline{1,k} \end{aligned} \right] p_{xx_0} \prod_{i=1}^{k} \psi(x_{i-1}) \\ &\overset{(8)}{=} \psi(x) \sum _{k=0}^\infty \sum_{(x_0, \ldots, x_{k}) \in V^{k+1} } \phi (x_{k}) \mathbb P_{x_0} \left [ \begin{aligned} \tau &= k \\ X_i &= x_{i}, i = \overline{1,k} \end{aligned} \right] p_{xx_0} \prod_{i=0}^{k-1} \psi(x_{i}) \\ &\overset{(9)}{=} \psi(x) \sum_{y \in V} \sum _{k=0}^\infty \sum_{(x_1, \ldots, x_{k}) \in V^{k} } \phi (x_{k}) \mathbb P_{y} \left [ \begin{aligned} \tau &= k \\ X_i &= x_{i}, i = \overline{1,k} \end{aligned} \right] p_{xy} \prod_{i=0}^{k-1} \psi(x_{i}) \\ &= \psi(x) \sum_{y \in V} p_{xy} \sum _{k=0}^\infty \sum_{(x_1, \ldots, x_{k}) \in V^{k} } \phi (x_{k}) \mathbb P_{y} \left [ \begin{aligned} \tau &= k \\ X_i &= x_{i}, i = \overline{1,k} \end{aligned} \right] \prod_{i=0}^{k-1} \psi(x_{i}) \\ &= \psi(x) \sum_{y \in V} p_{xy} \sum _{k=0}^\infty \mathbb E_y \left [ \mathbf{1} {\{ \tau = k \}} \phi (X_{k}) \prod_{i=0}^{k-1} \psi(X_i) \right] \\ &= \psi(x) \sum_{y \in V} p_{xy} \mathbb E_y \left [ \phi (X_{\tau}) \prod_{i=0}^{\tau-1} \psi(X_i) \right] \\ &= \psi(x) \sum_{y \in V} p_{xy} u (y) \\ \end{aligned}$$
where
$(3)$: Because $x \in E^c$, $\mathbb P_x [\tau = 0] = 0$.
$(4)$: $\prod_{i=0}^{k-1} \psi(X_i) = \psi(X_0) \prod_{i=1}^{k-1} \psi(X_i)$ and conditional on $X_0 = x$, $\psi(X_0) = \psi(x)$, which is a constant and can be put outside $\mathbb E_x$.
$(5)$: Markov property.
$(6)$: Instead of $1$, we start the summation from $0$. As such, $k$ is replaced by $k+1$.
$(7)$: We replace $(x_1, \ldots, x_{k+1})$ by $(x_0, \ldots, x_{k})$.
$(8)$: $ \prod_{i=1}^{k} \psi(x_{i-1}) = \prod_{i=0}^{k-1} \psi(x_{i})$.
$(9)$: We replace $x_0$ by $y$ and separate $\sum_{(x_0, \ldots, x_{k}) \in V^{k+1}}$ into $\sum_{y \in V} \sum_{(x_1, \ldots, x_{k}) \in V^{k}}$.
Remark: If we would like to have the constant discounted factor $a^{\tau}$ instead of the random discounted factor $\prod_{i=0}^{\tau-1} \psi(X_i)$, we can define the function $\psi$ by $\psi (x) = a$ for all $x \in V$.
@Saad answered my question with his comments, so I post them here to close this question.