[proofplan] We first prove part (1): at least one state in a finite state space is recurrent. The argument is by contradiction. If every state were transient, then $p_{ij}(n) \to 0$ for each $j$ (from the [Generating Function Identity](/theorems/2212) and finiteness of $\sum_n p_{ij}(n)$). Summing over the finite state space gives $\sum_{j \in S} p_{ij}(n) \to 0$, contradicting the fact that this sum equals $1$ for all $n$. Part (2) follows from part (1) combined with the [class property of recurrence](/theorems/2214): an irreducible chain has a single communicating class, so either all states are recurrent or all are transient, and part (1) rules out the latter. [/proofplan] [step:Prove part (1): derive a contradiction from the assumption that all states are transient] Fix a starting state $i \in S$ and suppose for contradiction that every state $j \in S$ is transient. We show $p_{ij}(n) \to 0$ as $n \to \infty$ for each fixed $j$. Since $j$ is transient, the [Recurrence Summability Criterion](/theorems/2211) gives $\sum_{n=0}^{\infty} p_{jj}(n) < \infty$. The [Generating Function Identity](/theorems/2212) with parameter $s = 1$ gives \begin{align*} \sum_{n=0}^{\infty} p_{ij}(n) = P_{ij}(1) = \delta_{ij} + F_{ij}(1)\, P_{jj}(1). \end{align*} Since $F_{ij}(1) = \mathbb{P}_i(T_j < \infty) \leq 1$ and $P_{jj}(1) = \sum_n p_{jj}(n) < \infty$, we obtain $\sum_{n=0}^{\infty} p_{ij}(n) < \infty$. A convergent series of non-negative terms must have its general term tend to zero, so $p_{ij}(n) \to 0$ as $n \to \infty$. Now use finiteness of $S$. For every $n \geq 0$, the $n$-step transition probabilities from $i$ form a probability distribution on $S$: \begin{align*} \sum_{j \in S} p_{ij}(n) = 1. \end{align*} Since $S$ is finite, $|S| = N < \infty$, and we may interchange the limit and the finite sum: \begin{align*} \lim_{n \to \infty} \sum_{j \in S} p_{ij}(n) = \sum_{j \in S} \lim_{n \to \infty} p_{ij}(n) = \sum_{j \in S} 0 = 0. \end{align*} But $\sum_{j \in S} p_{ij}(n) = 1$ for all $n$, so the limit must be $1$. This is a contradiction, so the assumption that all states are transient is false. At least one state in $S$ is recurrent. [guided] The key insight is that in a finite state space, probability cannot "escape to infinity." If all states were transient, each individual state would receive vanishing probability as $n \to \infty$, but the total probability must remain $1$. Suppose for contradiction that every $j \in S$ is transient. Fix any starting state $i$. For each $j$, transience means $\sum_n p_{jj}(n) < \infty$ by the [Recurrence Summability Criterion](/theorems/2211). Using the [Generating Function Identity](/theorems/2212) at $s = 1$: \begin{align*} P_{ij}(1) = \delta_{ij} + F_{ij}(1)\, P_{jj}(1). \end{align*} We have $F_{ij}(1) \leq 1$ (it is a probability) and $P_{jj}(1) < \infty$ (by the transience assumption). So $P_{ij}(1) = \sum_{n=0}^{\infty} p_{ij}(n) < \infty$. Since $p_{ij}(n) \geq 0$ for all $n$ and the series converges, the general term must tend to zero: $p_{ij}(n) \to 0$ as $n \to \infty$. This holds for each fixed $j \in S$. Now we exploit finiteness: since $|S| < \infty$, the sum $\sum_{j \in S}$ is a finite sum, and we may pass the limit through: \begin{align*} 1 = \sum_{j \in S} p_{ij}(n) \xrightarrow{n \to \infty} \sum_{j \in S} 0 = 0. \end{align*} This is a contradiction. Note that this argument fails for infinite state spaces: there, $\sum_{j \in S} p_{ij}(n) = 1$ is an infinite sum, and individual terms going to zero does not force the sum to go to zero (e.g., the mass could spread out over infinitely many states). This is precisely why transience is possible in infinite state spaces. [/guided] [/step] [step:Deduce part (2): irreducibility promotes the single recurrent state to universal recurrence] Suppose the chain is irreducible, meaning $S$ is a single communicating class. By part (1), at least one state $i_0 \in S$ is recurrent. By [Recurrence is a Class Property](/theorems/2214) (part 1), recurrence is preserved within a communicating class: since every $j \in S$ satisfies $j \leftrightarrow i_0$, every $j$ is recurrent. [guided] An irreducible chain has exactly one communicating class, namely $S$ itself. By the [class property of recurrence](/theorems/2214), within a communicating class, either all states are recurrent or all states are transient. Part (1) guarantees at least one state is recurrent, which rules out the "all transient" possibility. Therefore every state in $S$ is recurrent. This result highlights the sharp contrast between finite and infinite state spaces. In a finite irreducible chain, recurrence is guaranteed. In an infinite irreducible chain (such as the simple random walk on $\mathbb{Z}^d$ for $d \geq 3$), all states can be transient -- the probability mass escapes to infinity. [/guided] [/step]