Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
sorry, what do you mean by '!='? –  Berci Oct 2 '12 at 22:17
3  
@Berci: != is a fairly standard ASCII representation of $\ne$; I believe that it originated with the C programming language. –  Brian M. Scott Oct 3 '12 at 8:40
1  
@Brian: != was used already in B (but apparently not in BCPL which didn't have a not-equal-to operator). –  Henning Makholm Oct 3 '12 at 16:34
    
APL and one of the Algols had A≠B, PL/1 had ¬=. –  copper.hat Oct 5 '12 at 2:54
add comment

4 Answers

up vote 0 down vote accepted

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)$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

$\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$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.