Full Idea
There are atomic formulas, and formulas built from the connectives, and that is all. We show that all formulas have some property, first for the atomics, then the others. This proof is 'induction on complexity'; we also use 'recursion on complexity'.
Gist of Idea
'Induction' and 'recursion' on complexity prove by connecting a formula to its atomic components
Source
John P. Burgess (Philosophical Logic [2009], 1.4)
Book Reference
Burgess,John P.: 'Philosophical Logic' [Princeton 2009], p.4
A Reaction
That is: 'induction on complexity' builds a proof from atomics, via connectives; 'recursion on complexity' breaks down to the atomics, also via the connectives. You prove something by showing it is rooted in simple truths.