(Denne oppgaven er omtrent lik oppgave 12.1 i boken.)

La $f$ være en funksjon på bitstrenger definert rekursivt på følgende måte:

1. $f(\str{0})=\str{1}$ og $f(\str{1})=\str{0}$
2. $f(b\str{0})=f(b)\str{1}$, hvor $b$ er en bitstreng.
3. $f(b\str{1})=f(b)\str{0}$, hvor $b$ er en bitstreng.

Følgende er et induksjonsbevis for at $f(f(b))=b$ for alle bitstrenger $b$. Finn ut hva som skal stå i boksene.

Basissteget: Det er at holder for $b=\str{0}$ og $b=\str{1}$.

Ved å sette inn $\str{0}$ for $b$, får vi $f(f(\str{0}))=\str{0}$. Følgende utregning viser at dette er sant.

• $f(f(\str{0}))=f(\str{1})$ (ved punkt 1 i definisjonen av $f$)
• $=\str{0}$ (ved punkt 1 i definisjonen av $f$)

Ved å sette inn $\str{1}$ for $b$, får vi $f(f(\str{1}))=\str{1}$. Følgende utregning viser at dette er sant.

• $f(f(\str{1}))=f(\str{0})$ (ved punkt 1 i definisjonen av $f$)
• $=\str{1}$ (ved punkt 1 i definisjonen av $f$)

steget: Anta at påstanden holder for en bitstreng $b$, det vil si at $f(f(b))=b$. Dette er , og vi må fra denne vise at holder for en bitstreng $bx$, det vil si at $f(f(bx))=$, hvor $x$ enten er $\str{0}$ eller $\str{1}$. Vi får to tilfeller, ett for $x=\str{0}$ og ett for $x=\str{1}$.

Hvis $x=0$, får vi følgende.

• $f(f(b\str{0})) = f(f(b)\str{1})$ (ved punkt i definisjonen av $f$)
• $=f(f(b))\str{0}$ (ved punkt 3 i definisjonen av $f$)
• $=b\str{0}$ (ved induksjonshypotesen)

Hvis $x=\str{1}$, får vi følgende.

• $f(f(b\str{1})) = f$ () (ved punkt i definisjonen av $f$)
• $=f(f(b))\str{1}$ (ved punkt 2 i definisjonen av $f$)
• $=b\str{1}$ (ved induksjonshypotesen)

Ved følger det at $f(f(b))=$ for alle bitstrenger $b$.