Peter Smith’s approach is probably the best way to think about such problems in general. In this case there’s another fairly simple approach. Notice first that the connective $\#$ is symmetric in its three arguments: if $XYZ$ is any permutation of $ABC$, $\#ABC$ is equivalent to $\#XYZ$. From this it’s easy to see that all combinations of exactly two sentence letters $A$ and $B$ with $\#$ are equivalent either to $\#AAB$ or to $\#ABB$. Moreover, $\#AAB$ is equivalent simply to $A$, and $\#ABB$ to $B$; this suggests trying to show that as long as we work with at most two sentence letters, $\#$ essentially does nothing.
Claim: Every wff that can be constructed from the sentence letters $A$ and $B$ and the connectives $\neg$ and $\#$ is equivalent to one of $A,B,\neg A$, and $\neg B$.
Proof: The claim is easily proved by induction on the complexity of the wff. It’s certainly true for wffs with no connective: they are simply $A$ and $B$. Suppose that $\varphi$ has at least one connective. Then $\varphi$ is either $\neg\psi$ for some wff $\psi$, or $\#\psi_0\psi_1\psi_2$ for wffs $\psi_0,\psi_1$, and $\psi_2$. Suppose that $\varphi=\neg\psi$. The induction hypothesis ensures that $\psi$ is equivalent to one of $A,B,\neg A$, and $\neg B$, and $\varphi$ is therefore equivalent to one of $\neg A,\neg B,A$, and $B$, respectively.
Now suppose that $\varphi=\#\psi_0\psi_1\psi_2$. Again the induction hypothesis ensures that each of $\psi_0,\psi_1$, and $\psi_2$ is equivalent to one of $A,B,\neg A$, and $\neg B$. Any set of three chosen from $\{A,B,\neg A,\neg B\}$ necessarily contains either two copies of one of the four wffs or a wff and its negation, so $\varphi$ is equivalent to $\#XXY$ or $\#X\neg XY$ for some $X,Y\in\{A,B,\neg A,\neg B\}$. But $\#XXY$ is equivalent to $X$, and $\#X\neg XY$ is equivalent to $Y$, so in every case $\varphi$ is equivalent to one of $A,B,\neg A$, and $\neg B$. The claim now follows by induction. $\dashv$
Since $A\land B$ is not equivalent to $A,B,\neg A$, or $\neg B$, $\{\neg,\#\}$ is not complete.
(I’ve implicitly used the fact that if $\psi_0,\psi_1$, and $\psi_2$ are equivalent to $\psi_0',\psi_1'$, and $\psi_2'$, respectively, then $\#\psi_0\psi_1\psi_2$ is equivalent to $\#\psi_0'\psi_1'\psi_2'$. This is clear from consideration of the relevant truth tables.)
You certainly have the right idea ... but there is just one small problem with the case of the negation. You say to consider the 'two predecessors' of $\beta$ ... but what if $\beta$ is a negation itself?
Fortunately, the proof is easily fixed ... instead of performing induction on the number of sentence symbols, simply perform induction on the length of the statements, i.e. the number of sentence symbols plus the number of logical operators that are in the expression.
Best Answer
I assume that a wff is either
Then use structiral induction to show
Proposition. If $\alpha$ is a wff then its length $L(\alpha)$ is in $\mathbb N\setminus\{2,3,6\}$
Proof: We assume that $L(\alpha)\in\mathbb N$ is already known, so it suffices to show $L(\alpha)\notin\{2,3,6\}$.
Proposition. If $n\in\mathbb N\setminus\{2,3,6\}$, then there exists a wff $\alpha$ with $L(\alpha)=n$.
Proof: $A$, $(\neg A)$, $(A\land A)$ are examples of lengths $1,4,5$. $((A\land A)\land A)$ is of length $9$ Since negating increases the length by $3$, we can obtain any length $n=4+3k$ and any length $n=5+3k$ and any lenbgth $n=9+3k$ with $k\ge 0$.