If $T_n=\sum_{k=1}^nX_k$ is a renewal process where $X_k$ are identical and independent with values in the positive integers, and $N(t)=\max\{j:T_j\leq t\}$ is the associated counting process, define $C_t=t-T_{N(t)}$ to be the "age" at time $t\in \mathbb{N}$. I'm wondering how to show rigorously that $C_t$ is a Markov chain.
Heuristically, I can see that $C_{t+1}$ is $C_t+1$ if there is no renewal at $t+1$ and $0$ if there is a renewal at $t+1$, and that the probability of a renewal at $t+1$ should depend on the location of the last renewal and the renewals before that should be irrelevant. But I don't know how to make this "rigorous" or calculate the transition probabilities. So my questions are: what is a rigorous proof that $\{C_t\}$ satisfies the Markov property, and how do you calculate the transition probabilities \begin{align*} \Pr(C_{t+1}=i+1|C_t=i),\\ \Pr(C_{t+1}=0|C_t=i). \end{align*} The texts I'm reading treat this as easy enough to leave out the details, but I haven't grasped it yet.
This just summarizes my comments to formally provide an answer. Let $t$ be a positive integer. For a given trajectory $i_0, i_1, ..., i_{t-1}$ of the $C_t$ process, define the history event $$H = \{C_j = i_j \: \forall j \in \{0, 1, ..., t-1\}\}$$
Easy way:
Let $i \in \{0, 1, 2, ...\}$. Then $$ P[C_{t+1}=0|C_t=i, H] = P[X_1=i+1|X_1>i] $$ and so this is conditionally independent of the history $H$, given that $C_t=i$.
More formal:
You can condition on $N_t=k$ and $(X_1, ..., X_k)=x$ for all $k \in \{0, 1, 2, ...\}$ and $x \in \mathbb{Z}^k$.
\begin{align*} &P[C_{t+1}=0|C_t=i, H] \\ &= \sum_{k=0}^{\infty} \sum_{x \in \mathbb{Z}^k} \underbrace{P[C_{t+1}=0|C_t=i, H, N_t=k, (X_1, ..., X_k)=x]}_{P[X_{k+1}=i+1|X_{k+1}>i]}P[N_t=k, (X_1, ..., X_k)=x|C_t=i, H]\\ &= P[X_1=i+1|X_1>i]\underbrace{\sum_{k=0}^{\infty} \sum_{x \in \mathbb{Z}^k}P[N_t=k, (X_1, ..., X_k)=x|C_t=i, H]}_{1} \end{align*} where (even more formally) we can restrict the double sum to consider only those $k$ and $x$ values that satisfy: $$P[N_t=k, (X_1, ..., X_k)=k|C_t=i, H]>0$$ and note that for such cases, the following two events are the same: \begin{align} &\{C_t=i, H, N_t=k, (X_1, ..., X_k) = x\} \\ &\{X_{k+1}>i, (X_1, ..., X_k)=x\} \end{align}