Infinite boolean sequence

Question

I was given the following problem:

Let $V_1, V_2, \dots$ be an infinite sequence of Boolean variables. For each natural number $n$, define a proposition $F_n$ according to the following rules:

$$\begin{align*} F_0 &= \text{False}\\ F_n &= (F_{n-1} \ne V_n)\;. \end{align*}$$

Use induction to prove that for all $n$, $F_n$ is $\text{True}$ if and only if an odd number of the variables $V_k \;( k \le n)$ are $\text{True}$.

Can anyone help me out with at least beginning this problem? I'm not even entirely sure what it is asking.

Answer 1

First, notice that for any boolean value $v$, we have $(\text{False} \neq v) = v$, and $(\text{True} \neq v) = \neg v$.

The base case for the induction is $F_1 = (F_0 \neq V_1) = (\text{False} \neq V_1) = V_1$. If $V_1$ is false, then an even number of values $(V_1)$ are true, if $V_1$ is true, then an odd number of values of $(V_1)$ are true. Hence the base case is true.

Now assume that $F_n$ is true iff odd number of values of $(V_1,...,V_n)$ are true. Then we have two cases to consider: (1) $V_{n+1}$ is false, in which case we have $F_{n+1} = F_n$, or equivalently $F_{n+1} = (F_{n-1} \neq V_n)$, and (2) $V_{n+1}$ is true, in which case we have $F_{n+1} = \neg F_n$ or again, $F_{n+1} = (F_{n-1} \neq V_n)$.

It follows that for all values of $V_n$ we have $F_{n+1} = (F_{n-1} \neq V_n)$.

Answer 2

So, given $V_i$ Boolean variables, i.e. all of them are either true or false, and you define 'propositions' $F_0,F_1,\dots$, they will be also evaluated as true or false (we can call it just another set of Boolean variables, built up using $V_i$), such that $$F_0:=\text{false}, \ F_1:=(F_0\ne V_1), \ F_2:=(F_1\ne V_2), \ \dots$$ Now you have to prove by induction that $$F_n=(\text{odd number of }V_k\text{'s are true, }k\le n)$$ It starts by observing that, as no $V_k$'s are given for $k\le 0$, the statement on the RHS is false ($0$ of $V_k$'s are true, but $0$ is even). Then assume the induction hypothesis for $n$ and try to deduce it for $n+1$.

Answer 3

$\newcommand{\T}{\text{True}}\newcommand{\F}{\text{False}}$The statement that you’re trying to prove for each $n\ge 0$ is:

$P(n):$ $F_n$ is $\T$ if and only if an odd number of the variables $V_k$ with $k\le n$ are $\T$.

To check the base case of your induction, observe that there are $0$ variables $V_k$ such that $k<0$ and $V_k$ is $\T$, since there are $0$ variables $V_k$ with $k<0$, and $0$ is an even number. Thus, the number of variables $V_k$ such that $k<0$ and $V_k=\T$ is not odd, and of course $F_0$ is not $\T$. Thus, $P(0)$ is true.

For the induction step, assume that $P(n)$ is true for some $n\ge 0$; we must show that $P(n+1)$ is also true. Let $m$ be the number of variables $V_k$ such that $k\le n$ and $V_k=\T$. We’ve assumed that $P(n)$ holds, so either $F_n$ is true and $m$ is odd, or $F_n$ is false and $m$ is even. Since $V_{n+1}$ can be either $\T$ or $\F$, we have four possibilities to consider:

1. If $F_n=\T$ (so $m$ is odd) and $V_{n+1}=\T$, then $F_n=V_{n+1}$, so $F_{n+1}=\F$. There are $m+1$ variables $V_k$ such that $k\le n+1$ and $V_k=\T$, and $m$ is odd, so $m+1$ is even. In this case $F_{n+1}=\F$ and the number of variables $V_k$ such that $k\le n+1$ and $V_k=\T$ is even, which is fine.

2. If $F_n=\T$ (so $m$ is odd) and $V_{n+1}=\F$, then $F_n\ne V_{n+1}$, so $F_{n+1}=\T$. There are still only $m$ $\T$ variables $V_k$ with $k\le n+1$, and $m$ is odd, so this case is also fine: $F_{n+1}=\T$, and the number of $\T$ variables $V_k$ with $k\le n+1$ is odd.

3. If $F_n=\F$ (so $m$ is even) and $V_{n+1}=\T$, then $F_n\ne V_{n+1}$, so $F_{n+1}=\T$. There are $m+1$ $\T$ variables $V_k$ with $k\le n+1$, and $m$ is even, so $m+1$ is odd, and again we’re in good shape: $F_{n+1}=\T$, and the number of $\T$ variables $V_k$ with $k\le n+1$ is odd.

4. If $F_n=\F$ (so $m$ is even) and $V_{n+1}=\F$, then $F_n=V_{n+1}$, so $F_{n+1}=\F$. There are still only $m$ $\T$ variables $V_k$ with $k\le n+1$, and $m$ is even, which is again what we need: $F_{n+1}=\F$, and the number of $\T$ variables $V_k$ with $k\le n+1$ is even.

It follows that $P(n+1)$ holds, and by induction $P(n)$ holds for all $n\ge 0$.

Answer 4

A quicker way to see intuitively that this works is to notice that if we represent "False" by the number $0$ and "True" by the number $1$, then $\neq$ corresponds exactly to addition modulo $2$.

Therefore $F_n$ is represented by the sum of $V_1$ upto $V_n$ modulo 2, which is $1$ exactly if an odd number of the $V_i$s are $1$.