Pentagontall rekursiv og induksjon

a) \(P_1 = 1\), \(P_n = P_{n-1} + 5(n-1)\) for \(n \geq 2\)
b) \(\underline{\underline{P_{100} = 24751}}\)
c) \(\underline{\underline{P_n = \dfrac{5n^2 - 5n + 2}{2}}}\)

a

Vi observerer differansene mellom påfølgende pentagontall:

Mønsteret er at \(P_n - P_{n-1} = 5(n-1)\), altså legger man til \(5(n-1)\) kuler for å gå fra figur \(n-1\) til figur \(n\).

Rekursiv sammenheng:

b

Vi bruker den rekursive sammenhengen fra a) direkte i et program:

P = 1
for n in range(2, 101):
    P = P + 5*(n-1)
print(P)

Programmet gir \(\underline{\underline{P_{100} = 24751}}\).

c

Vi bruker teleskopsummering. Fra den rekursive sammenhengen får vi:

Eksplisitt formel: \(\underline{\underline{P_n = \dfrac{5n^2 - 5n + 2}{2}}}\)

Kontroll: \(P_5 = \dfrac{5 \cdot 25 - 25 + 2}{2} = \dfrac{102}{2} = 51\) ✓

Induksjonsbevis

Vi skal bevise at \(P_n = \dfrac{5n^2 - 5n + 2}{2}\) for alle \(n \geq 1\).

Grunntrinn (\(n = 1\)):

Induksjonssteg: Anta at påstanden holder for \(n = k\), det vil si at

Vi skal vise at den da også holder for \(n = k+1\), altså at \(P_{k+1} = \dfrac{5(k+1)^2 - 5(k+1) + 2}{2}\).

Fra den rekursive sammenhengen i a) har vi \(P_{k+1} = P_k + 5k\). Vi setter inn induksjonshypotesen:

Vi sjekker at dette stemmer overens med formelen for \(n = k+1\):

De to uttrykkene er like, så induksjonssteget er vist. ∎

Ved induksjonsprinsippet gjelder dermed \(P_n = \dfrac{5n^2 - 5n + 2}{2}\) for alle \(n \geq 1\).

a) (2 poeng) Det gis 1 poeng for rett rekursiv sammenheng og 1 poeng for en god begrunnelse.
b) (2 poeng) Dersom kandidaten har en riktig strategi, men gjør tellefeil eller programmeringsfeil, kan det gis 1 poeng.
c) (2 poeng) Det gis 1 poeng for rett formel for \(P_n\) og 1 poeng for induksjonsbeviset.