La S være et språk over $\{ \text{a}, \text{b} \}$ definert induktivt som den minste mengden slik at $\Lambda \in S$, og hvis $t \in S$, så $\text{a}t\text{a} \in S$ og $t\text{b} \in S$. Noen av strengene i $S$ er da $\Lambda$, $\text{aa}$, $\text{b}$, $\text{aab}$, $\text{aba}$, $\text{aaaa}$ og $\text{aaaba}$. Er du enig i at alle strenger i $S$ består av et partall antall $\text{a}$-er? Hva er det i så fall som gjør at du blir overbevist om det? Hvordan ville du argumentert for å overbevise noen andre om det samme?

Tenk over spørsmålene over før du leser videre!

Du vil sannsynligvis vise til at man alltid legger til 2 $\text{a}$-er når man legger til $\text{a}$-er i induksjonssteget i den induktive definisjonen av $S$. Siden det er et partall antall $\text{a}$-er i den ene strengen i basismengden, $\Lambda$, vil det ikke være mulig å ende opp med en streng med et oddetall antall $\text{a}$-er ved å bruke operasjonene i induksjonssteget. Det er denne intuitive ideen vi kan formalisere i et induksjonsbevis for at alle strenger i $S$ inneholder et partall antall $\text{a}$-er. Her er et slikt induksjonsbevis:

Påstanden vi skal bevise er at alle strenger i $S$ inneholder et partall antall $\text{a}$-er.

Basissteget er å vise at påstanden holder for alle elementene i basismengden, altså for strengen $\Lambda$. Den tomme strengen inneholder $0$ $\text{a}$-er, og $0$ er et partall, så påstanden er sann for alle elementene i basismengden.

Induksjonssteget er å vise at hvis påstanden er sann for en streng $t$, så er påstanden sann for strengene $\text{a}t\text{a}$ og $t\text{b}$. Induksjonshypotesen her er altså at det er partall antall $\text{a}$-er i strengen $t$. La oss kalle dette antallet $\text{a}$-er for $x$. Da er det $x + 2$ $\text{a}$-er i strengen $\text{a}t\text{a}$. Siden $x$ er et partall, må $x + 2$ også være et partall. Dermed er det også et partall antall $a$-er i $\text{a}t\text{a}$. Videre er det $x$ $\text{a}$-er i strengen $t\text{b}$, for $t\text{b}$ inneholder nøyaktig like mange $\text{a}$-er som det er i strengen $t$, og $x$ er igjen er partall. Vi har da vist at hvis det er et partall antall $\text{a}$-er i strengen $t$ så er det et partall antall $\text{a}$-er i strengene $\text{a}t\text{a}$ og $t\text{b}$. Dermed har vi fullført induksjonssteget.

Ved strukturell induksjon følger det at alle strenger i $S$ inneholder et partall antall $\text{a}$-er.