I have two inductively defined operations:
$\text{bin}$
base case:
If $p$ is a propositional letter, then $\text{bin}(p) = 0$
inductive step
$\text{bin}(\neg \phi) = \text{bin} (\phi)$
$\text{bin}(\phi \wedge \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$
$\text{bin}(\phi \vee \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$
$\text{bin}(\phi \rightarrow \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$
$\text{bin}(\phi \leftrightarrow \psi) = \text{bin}(\phi) + \text{bin}(\psi) + 1$
$S$, which is defined as
$S(p) = \emptyset$
$S(\neg \phi) = S(\phi)$
$S(\phi \square \psi) = S(\phi) \cup S(\psi) \cup \{\phi, \psi\}$ where $\square$ can be $\wedge, \vee, \rightarrow or\leftrightarrow$
The inductive proof I have to give: Let bin($\phi$) be equal to the number of binary connectives in $\phi$, and |V| the number of elements of the set V.
Prove with induction that the following inequality holds for every propositional formula $\phi$: |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$).
For the base case, I have the following:
Base case:
If $\phi$ is an atomic propositional formula, then bin($\phi$) = 0 and |S($\phi$)| = |$\emptyset$| = 0, and so |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$) holds.
Inductive step:
I have no idea how to tackle this, but I have to prove for negation and for the binary connectives.
I would say I would start with:
"Assume the inductive hypothesis is true, i.e., |S($\phi$)| $\leq$ 2 $\cdot$ bin($\phi$) is true", or, maybe better, "Assume the property holds for formulas $\phi$ and $\psi$"
Then, case negation: S($\neg \phi$) = S($ \phi$) and bin($\neg \phi$) = bin($ \phi$), and therefor the property holds for $\neg \phi$
Then, case conjunction: bin($\phi \wedge \psi$) = bin($\phi$) + bin($\psi$) + 1, and S($\phi \wedge \psi$) = S($\phi$) $\cup$ S($\psi$) $\cup$ {$\phi$, $\psi$}.
Now, what I think I see is that with the operation bin 1 gets added, and with S *two* elements are added to the set. I just don't know how to formulate this nicely.