If $m_n + n$ is true, then prove that $m_{n+1} + n + 1$ is true. Algebraic breakdown help

So if I understand correctly you want to see the truth of the biconditional

$$P leftrightarrow p_{n+1}$$ where $P$ itself is a complex chain of smaller statements with arrows between them. The beauty of the situation is that you discovered the a different way of describing the truth or falsehood of $P$: $P$ is true if $m_n + n$ is even and false if it is odd.

This is great. Now we don't have to worry about the inner structure of $P$ and just role with this.

We know that there are just 4 possible situations:

• $P$ is true and $p_{n+1}$ is true
• $P$ is true and $p_{n+1}$ is false
• $P$ is false and $p_{n+1}$ is true
• $P$ is false and $p_{n+1}$ is false

In each of the four situations you can compute two things:

1. Whether the 'big' statement $P leftrightarrow p_{n+1}$ is true or not.

2. Whether $(n+1) + m_{n+1}$ is even or odd

Once you have done that you can check if the relation between truth/falsehood of the big statment and even/oddness (parity) of $(n+1) + m_{n+1}$ that you conjectured holds in all four cases and if it does you are done.

Now I think you don't have any trouble with item 1. So let's talk about 2.

First: why $(n+1) + m_{n+1}$? Well because there are $n + 1$ terms in the big statement $P leftrightarrow p_{n+1}$

As I said you want to compute this quantity in four situations. I'll do the first, you can do the other three.

$P$ is true so $n + m_n$ is even. Let's distinguish two more cases: $n$ even and $n$ odd.

If $n$ is even then $m_n$, the number of true statements among $p_1, ldots, p_n$ must be even as well. Now we add the aditional true (IN THIS CASE) statement $p_n$ so we get that $m_{n+1} = m_n + 1$: the total number of true statments is one more so $m_{n+1}$ is odd. On the other hand, since $n$ is even, $n+1$ is odd as well and hence $(n+1) + m_{n+1}$ is odd + odd = even.

If $n$ is odd then, since $n + m_n$ is even, $m_n$ is odd as well. We add one more true statement ($p_n$) so we find (IN THIS CASE) that $m_{n+1}$ is even. But $n + 1$ is even as well (since $n$ is odd) so again $(n+1) + m_{n+1}$ is even.

Conclusion: in the scenario of the first bullet point we have that $(n+1) + m_{n+1}$ is even. One down, three to go.