This paper describes a series of empirical studies, over a period of three years, designed to investigate the nature of learners’ difficulties with the proof technique of structural induction. The learners concerned were second‐year university students who had all completed a course in discrete mathematics and were currently attending a first course in Formal Methods of Computer Science. The main findings are applicable to both mathematical and structural induction, and can be ascribed to conceptual gaps. The precise nature of the errors made varied with the task and the teaching context, but a constant factor across all the studies was the failure of the majority of the subjects to appreciate the role of implication in induction. We suggest that this may be due, in part, to the conceptual gap between the main goal of the proof and the subgoals; the main goal might give false cues as to the structure of the subgoals. Another difficulty seen concerned the conceptual gap between knowing how to apply the principle of induction and understanding why it is valid. Our data indicate that performance may be improved by shifting teaching emphasis and by drawing learners’ attention to the structure of a recursive definition.