Induction on a well-formed formula (wff) Let α be a well-formed formula (wff); let c be the number of places at which binary connective symbols (∧, ∨, →, ↔) occur in α; let s be the number of places at which sentence symbols occur in α. (For example, if α is (A → (¬A)) then c = 1 and s = 2.) Show by using the induction principle that s = c + 1.
I'm not sure how to apply induction in this case.  Would the base case be c = 1 and s = 2?  Where would I go from there?  
 A: We proceed by induction on $c \in \{0,1,2,...\}$.
Base Case: Suppose $c=0$. Then since there are no binary connectives, $\alpha$ must be a literal (it is either an atom or its negation). Hence, we have $s = 1 = 0 + 1 = c + 1$, as desired.
Induction Hypothesis: Assume that the claim holds true for all $c \in \{0,1,...,k\}$.
It remains to prove the claim true for $c=k+1$. Suppose $\alpha$ has $k+1$ binary connective symbols. Then we can write $\alpha = \beta \circ \gamma$, where:


*

*The symbol $\circ$ is a placeholder for a binary connective (that is, $\circ\in \{\land, \lor, \to, \leftrightarrow\}$).

*$\beta$ is a wff that contains $x$ binary connectives, where $x \in \{0,1,...,k\}$.

*$\gamma$ is a wff that contains $y$ binary connectives, where $y \in \{0,1,...,k\}$.

*$x+y=k$


Thus, by the induction hypothesis, there are $x+1$ places at which sentence symbols occur in $\beta$ and $y+1$ places at which sentence symbols occur in $\gamma$. But then there must be:
$$
s=(x+1)+(y+1) = (x+y)+2=k+2 = (k+1)+1=c+1
$$
places at which sentence symbols occur in $\alpha$, as desired. This completes the induction.
