Let $X$ be the random variable counting the number of fair coin tosses until 'heads' appears for the first time. Let $(Y_n)_{n \ge 1}$ be the number of fair coin tosses until 'heads' appears $n$ times. Hence, $Y_{n+1}= Y_n + X_{n+1}$, where $(X_n)_{n \ge 1}$ are i.i.d random variables of the same distribution of $X$.
(a) Is $(Y_n)_{n \ge 1}$ a Markov chain?
(b) Is $(Y_n)_{n \ge 1}$ stationary?
My thoughts so far:
(a)
Since $Y_{n+1}$ directly depends on $Y_n$, I assume the process to be indeed a Markov chain. I also tried to find a transition matrix $P$ but I don't know if it's correct:
$$P = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0& \cdots & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$ So the idea is that one either stays in the current state or advances if another 'heads' comes up until one has $n$ heads.
(b)
Unfortunately I can't really answer this question as I've not grasped the concept of stationarity yet. I already know how to calculate the stationary distribution given a specific transition matrix but not how to argue whether it actually exists. Also, I didn't come to a proper result when I tried to calculate the stationary distribution of the matrix above, so I assume it either doesn't exist, the matrix is incorrect or I made a mistake.
I don't think your transition matrix is correct. Re-think what values $Y_n$ can take and what the states of your purported Markov chain would be.
You can directly check the Markov property by computing $$P(Y_{n+1} = y_{n+1} \mid Y_n = y_n, Y_{n-1} = y_{n-1}, \ldots, Y_1=y_1)$$ and checking whether it only depends on $y_n$ and $y_{n+1}$.
Try to just write down the definition of stationarity and see whether it holds. If you want to start with a sanity check, ask yourself if you think the distribution of $Y_{10}$ is the same as the distribution of $Y_{100}$.