Redigerer Tårnet i Hanoi (avsnitt)

===Matematisk bevis på den rekursive løsningen===
Man finner en løsning lettere ved å løse en mer generell oppgave: Hvordan flytte et tårn med h (h=høyde) skiver fra en start-pinne '''A''' (f=fra) til pinnen '''C''' (t=til). '''B''' er den gjenværende tredje pinnen hvor t≠f. Oppgaven er symmetrisk for [[permutasjon]]er av pinnenes navn ([[symmetrisk gruppe|symmetrisk gruppe S<sub>3</sub>]]). Hvis en løsning er kjent for å forflytte tårnet fra '''A''' til '''C''', kan samme løsning benyttes fra enhver annen start-pinne og mål-pinne. Hvis det bare er én skive (eller ingen skiver), er oppgaven triviell. Hvis n=1, flyttes disken fra '''A''' til '''C'''. Hvis h>1, må den største skiven flyttes fra '''A''' til en annen pinne, og helst til '''C''', et eller annet sted i sekvensen av forflytninger. Den eneste situasjonen som tillater denne forflytningen er når alle mindre h-1 skiver er på pinne '''B'''. Derfor må først alle n-1 mindre skiver flyttes fra '''A''' til '''B'''. Flytt deretter den største skiven og til slutt n-1 mindre skiver fra '''B''' til '''C'''. Tilstedeværelsen av den største skiven tvinger ikke frem noen forflytning av de n-1 mindre skivene og kan midlertidig ignoreres. Oppgaven er nå blitt redusert til å forflytte n-1 skiver, først fra '''A''' til '''B''' og deretter fra '''B''' til '''C'''. Den samme strategien kan brukes for å redusere h-1 til h-2, h-3, og så videre inntil h=1. Dette kalles [[rekursjon]]. Algoritmen identifiserer skivene etter stigende størrelse ved å nummerere dem med [[naturlig tall|naturlige tall]] fra 0 til h-1, der 0 er den minste og h-1 den største skiven.

Følgende prosedyre flytter et tårn med h skiver fra pinne '''f''' til en pinne '''t''', med '''r''' som den gjenværende tredje pinnen:

*Trinn 1: Hvis n>1, bruk først denne prosedyren til å forflytte de n-1 mindre skivene fra '''A''' til '''B'''. 
*Trinn 2: Flytt den største skiven, skive n-1 fra '''A''' til '''C'''. 
*Trinn 3: Hvis h>1 benytt denne prosedyren på nytt for å forflytte de h-1 mindre skivene fra ''' B''' til '''C'''.

[[Matematisk induksjon]] beviser at prosedyren krever det minste antall mulige forflytninger, og at løsningen er den eneste med dette minimumstall av forflytninger. Ved hjelp av [[differensekvasjon]]er, kalkuleres antall forflytninger av <big><math>2^h - 1</math></big>. Trinnene 1 og 3 krever <big><math>T_{h-1}</math></big> forflytninger, og trinn 2 krever én forflytning, som gir:
:<big><math>T_h = 2T_{h-1} + 1</math></big>.