Length of a formula in propositional logic I've seen the following problem on a past exam question:
Show that the length of a formula in $\mathscr{L}$ is equal to $4m+n+1$, where $m$ is the number of binary connectives and $n$ is the number of negation symbols in the formula
Thoughts
There are quite a few cases to consider, but the $n=m=0$ and $m=0\neq n$ cases are simple. So we are left to deal with the $n,m \neq 0$ case.
I think the key thing is realise that formulas are composed of strings of the type 
$$(p \star q)$$ for a binary connective $\star$ and formulas $p$ and $q$. We can of course throw a negation sign in front of this, but these 'substrings' of the formula seem to be key to cracking this to me, for each gives rise to $5$ symbols, although potentially $p$ or $q$ will itself by a $5$-long string embedded in the formula.
I really can't see how this general rule can be proved though. Perhaps an inductive approach is best? A solution to this problem would be very interesting to me.

Use structural induction.
Use that a formula $\alpha$ is either of the form 


*

*$p$ or any other (atomic) variable

*$\neg \beta$ where $\alpha$ is a formula or

*$(\gamma\star \beta)$ where $\gamma,\beta$ are formulas and $\star$ is a binary connective.


The numbers $n(\alpha)$, $m(\alpha)$ and length $L(\alpha)$ obey the recursions


*

*$n(\alpha)=m(\alpha)=0$, $L(\alpha)=1$ if $\alpha=p$

*$n(\alpha)=n(\beta)+1$, $m(\alpha)=m(\beta)$, $L(\alpha)=L(\beta)+1$

*$n(\alpha)=n(\beta)+n(\gamma)$, $m(\alpha)=m(\beta)+m(\gamma)+1$, $L(\alpha)=L(\beta)+L(\gamma)+4$


in the respective cases.
