How do I write a proof using induction on the length of the input string?

Question Detail: 

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however when strings come into play I get real tripped up. I'd really appreciate it if someone would go through the process of making such a proof step by step.

Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):

Consider the DFA with the following transition table:

         0    1        ________ -> A |  A    B   *B |  B    A 

Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.

This is an answered problem in the book, so I'm not looking for someone to do my homework. I just need someone to explain it to me straight.

Book's Answer: (taken from here)

The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's. Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.

Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.

• Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.

• Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(A,z) = A, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case as well, δ-hat(A,w) = A if and only if w has an even number of 1's.

I understand how to prove things like $\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$ using induction. I'm just confused by how this works with building strings. I'm confused by the bolded parts. I don't understand how they are come up with/how it actually proves what is accepted/how it is inductive.

δ-hat is the extended transition function, by the way.

Asked By : tcdowney

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4905

Answered By : Raphael

^{As it is unclear where your problem lies, I'll start at the very beginning.}

Mathematical induction works like the game of Chinese whispers (in the ideal case, that is all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.

More formally, every induction proof consists of three basic elements:

• Induction anchor, also base case: you show for small cases¹ that the claim holds.
• Induction hypothesis: you assume that the claim holds for a certain subset of the set you want to prove something about.
• Inductive step: Using the hypothesis, you show that the claim holds for more elements.

Of course, the step has to be tuned such that it covers the whole base set (in the limit).

Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is not recommended when doing proofs yourself, especially as a beginner. Write down everything.

---

Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.

• Anchor: For $n=0$, $\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$ clearly holds.
• Hypothesis: Assume that $\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$ holds for an arbitrary, but fixed² $n \in \mathbb{N}$.

• Step: For $n+1$, compute the sum:

  $\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$

  So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)

The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.

---

Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.

• Anchor: Consider the (only) set of size $0$, the empty set. Clearly, $2^\emptyset = \{\emptyset\}$ and therefore $|2^\emptyset| = 1 = 2^0$ as claimed.
• Hypothesis: Assume that for all sets $A \subseteq \mathbb{N}$ with $|A| \leq n$ with some arbitrary, but fixed $n \in \mathbb{N}$, we have $|2^A| = 2^|A|$.

• Step: Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 > 0$). Now the hypothesis applies to $B \setminus \{b\}$ and thus $|2^{B \setminus \{b\}}| = 2^n$. Since

  $\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$,

  we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.

Again, by induction the claim is proven.

---

Now, for your problem can use a common trick: strengthening the statement. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.

Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.

• Anchor: After processing the only string of length zero, $\varepsilon$, the automaton is clearly in state $A$ as claimed.
• Hypothesis: Assume that claim holds for input fragments of length up to $n$ which is chosen arbitrarily, but fixed.
• Step: Consider an arbitrary word $w \in \{0,1\}^{n+1}$. There are two cases.
  1. $w$ contains an even number of ones. There are two cases for the last symbol.
     1. $w_n = 0$: In this case, $w' = w_1 \dots w_{n-1}$ contains an even number of ones. By induction hypothesis, the automaton is in state $A$ after consuming $w'$. Consuming $w_n = 0$ causes the automaton to stay in state $A$, as claimed.
     2. $w_n = 1$: In this case, $w' = w_1 \dots w_{n-1}$ contains an odd number of ones. By induction hypothesis, the automaton is in state $B$ after consuming $w'$. Consuming $w_n = 1$ causes the automaton to switch to state $A$, as claimed.
  2. $w$ contains an odd number of ones. Similar to case 1.

The principle of induction implies that the claim indeed holds.

---

1. You perform induction along some partial order; the anchor needs to cover all minimal elements, and sometimes more (depending on the statement).
2. The "arbitrary, but fixed" is essential! We can not change $n$ in the step and treat it as if it were a fixed number, but we can also not assume anything about it.
3. Denoting the power set with $2^A$ may seem weird. It is rooted in the observation that the power set is equivalent to the set of all functions from $A$ to ${0,1}$, which is denoted thus.
4. Choosing $B$ arbitrary is essential for covering the whole space. One may be tempted to say, "Take any such $A$ and add an element that was not there before.". In this case, that would do the same, but it can be easy to get wrong in more complicated settings (e.g. adding nodes to graphs). Always take an arbitrary larger object and then cut it apart to apply the hypothesis on its parts; never assemble the larger object from smaller which are covere by the hypothesis.