Xrfgtjtk

A square board is divided into 16 equal squares by lines drawn parallel to its sides. A counter is placed at random on one of these squares and is then moved n times. At each of these moves, it can be transferred to any neighbouring square, horizontally, vertically, or diagonally, all such moves being equally likely.

Let $c_{n}$ be the probability that a particular corner site is occupied after n such independent moves, and let the corresponding probabilities for an intermediate site at the side of the board and for a site in the middle of the board be $s_{n}$ and $m_{n}$, respectively. Show that $$4c_{n}+8s_{n}+4m_{n} = 1, n =0,1,2,...$$
and that
$$ c_{n}=frac{2}{5}s_{n-1}+frac{1}{8}m_{n-1}, n = 1,2,...$$
Find two other relations for $s_{n}$ and $m_{n}$ in terms of $c_{n-1}, s_{n-1},$ and $m_{n-1}$ -> ok, I found it

And hence find $c_{n},s_{n},$ and $m_{n}$. -> how to do it by iteration ? and in what form should be the final answer ?

edit : I don't ask you to resolve it for me, i would like to receive a hint, I am not used to the linear recurrence relation.
I am lost and I don't know what to do. I substituted the $m_{n-1}$ and $s_{n-1}$ in $c_{n}$, do I need to make an induction proof ? Do I need to use a special method ?

The first statement, $$4c_n + 8s_n + 4m_n = 1$$ is simply the statement that the counter must be on the board after $n$ moves. This should be obvious if you draw out the $4times4$ board and label the squares with $c,m$ and $s$. At this step it's also worth noting that since the counter is placed on the board at random (i.e. all squares can be chosen equally) we have $$c_0 = s_0 = m_0 = 1/16$$

For the second statement, we look at how at counter can, on the $n^{mbox {th}}$ turn move to a corner square. There are three squares adjacent to a corner, two side squares and one middle-square. So if the counter was on a side square on at the end of move $n-1$ it has $5$ squares it can move to on move $n$, one of which is our corner square. Similarly, if it's on the middle square there is a $1/8$ chance of the counter moving to our corner square. So, $$c_n = frac{2}{5}s_{n-1} + frac{1}{8}m_{n-1}$$
where the factor of $2$ comes from there being two side squares that can reach the corner.

You say you've found the formulae for $s_n$ and $m_n$ so I won't take this further, but they're done using the same considerations: where can the counter be at the end of move $n-1$? and what's the probability of it moving onto a side (or middle) square?

So, to complete finding $c_n, s_n$ and $m_n$ you need to use the initial state: $c_0, s_0$ and $m_0$ and your formulae. We know that $$c_n = frac{2}{5}s_{n-1} + frac{1}{8}m_{n-1}$$ so we have that $$c_1 = frac{2}{5}cdot frac{1}{16} + frac{1}{8}cdot frac{1}{16} = frac{21}{640}$$ For $c_2$ you have to substitute in your formulae for $s_1$ and $m_1$ and then solve for $c_2$. This can then be generalised to allow you to solve for $c_n$, $s_n$ and $m_n$.