LEKTION 03-11

Rekursion

En talföljd kan defineras genom att man anger en explicit formel. Till exempel betrakta sekvensen

{a_{n} = n^{2}}_{n∈ℕ}

Men det är mycket vanligt att talföljden defineras via en rekursions formula. Det betyder att man anger hur varje element kan beräknas ur den föregående element. Ett exempel är:

a_{n} = a_{n−1} + 2n − 1 för n ≥ 1 och a_{0} = 0

a_{0} = 0 kallas begynnelsevärde.

Detta anger följden {0, 1, 4, 9, 16, ...}.

Man kan ha mer komplicerade rekursion formuler. Fibonacciföljden är ett exempel på följd där man behover två föregående element fr̈ att beräkna den följande element:

\{ \begin{matrix}F_{n} & = & F_{n−1} + F_{n−2} & n ≥ 2 \\ F_{1} & = & 1 \\ F_{0} & = & 0 \end{matrix}

Induktion

Vi ska använda symboler ∑ och Π på följande sätt.

• ∑_{i=1}^{n} s_{i} = s_{1} + ... + s_{n}

• Π_{i=1}^{n}s_{i} = s_{1} · ... · s_{n}. Exempel.

∑_{i=1}^{n} i^{2} = 1 + 4 + 9 + 16 + ... + n^{2}

Vi har att • Om n = 1 då blir summan 1 = \frac{1(1+1)(2·1+1)}{6},

• Om n = 2 då blir summan 5 = \frac{2(1+2)(2·2+1)}{6},
• Om n = 3 då blir summan 14 = \frac{3(1+3)(2·3+1)}{6}.

1

Hur kan man visa att:

∑_{i=1}^{n} i^{2} = \frac{n(1 + n)(2 · n + 1)}{6} gäller för n ≥ 1?

När vi vill visa att en sats P (n) gäller för alla naturliga tal n ≥ a är det ofta bra att använda INDUKTIONSPRINCIPEN:

(1) visa P (a) gäller, dvs visa att satsen är sant för n = a. Detta kallas bassteget.

(2) Antag P (n) gäller för n ≤ k och visa P (k + 1), dvs antag att satsen är sant för n ≤ k och visa sedan den for n = k + 1

När man har verifierat steg (1) och (2) har man , enligt induktions pricipen, visat satsen gäller för alla n ≥ a.

BEVIS: Vi ska bevisa att ∑_{i=1}^{n} i^{2} = \frac{n(1+n)(2·n+1)}{6} för n ≥ 1.

(1) Detta är sant för n = 1 (vi beräknade det).

(2) Antag att

∑_{i=1}^{n} i^{2} = \frac{n(1 + n)(2 · n + 1)}{6} gäller för n ≤ k

Vi ska visa att

∑_{i=1}^{k+1} i^{2} = \frac{(k + 1)(1 + k + 1)(2 · (k + 1) + 1)}{6} = \frac{(k + 1)(k + 2)(2k + 3)}{6}

Vi har att:

∑_{i=1}^{k+1} i^{2} = ∑_{i=1}^{k} i^{2} + (k + 1)^{2} = \frac{k(1 + k)(2 · k + 1)}{6} + (k + 1)^{2}

Och då

∑_{i=1}^{k+1} i^{2} = \frac{(1 + k)[k(2 · k + 1) + 6(k + 1)]}{6} = \frac{(1 + k)(2k^{2} + 7k + 6)}{6} =

= \frac{k + 1(1 + k + 1)(2 · (k + 1) + 1)}{6}

Så, enligt induktionsprincipen gäller ∑_{i=1}^{n} i^{2} = \frac{n(1+n)(2·n+1)}{6} för alla n ≥ 1.

Exempel: Beviset av en del av välordningspricipen.

Vi vill visa att alla icke-tomma ändliga delmängder B av ℤ^{+} innehåller ett minsta element.

Vi ska visa den med hälp av induktion på kardinaliteten av delmägden.

(1) Om |B| = 0 det finns ingenting att visa, så satsen är sant.

(2) Antag att satsen är sant för varje delmängd B med kardinaliteten ≤ k. Vi ska visa att satsen är sant för varje B med |B| = k + 1. Betrakta en delmängd B = {a_{1}, ..., a_{k+1}}. Enligt induktionsantagandet har delmängden {a_{1}, ..., a_{k}} ett minsta element m. Om m ≤ a_{k+1} så är m det minsta element av B. Annars är a_{k+1} < m som betyder att a_{k+1} är det minsta element av B.

Exempel. Visa att n^{2} > 7n + 1 för alla n ≥ 8.

(1) Satsen är sant för n = 8 eftersom 64 > 56 + 1.

(2) Antag n^{2} > 7n + 1 för alla n ≤ k. Vi ska visa att (k + 1)^{2} > 7(k + 1) + 1. På grund av induktionsantagandet är (k + 1)^{2} = k^{2} + 2k + 1 > 7k + 1 + 2k + 1. Då 2k-6har vi att (k + 1)^{2} > 7(k + 1) + 1 + (2k − 6) > 7(k + 1) + 1 eftersom k ≥ 8 gäller 2k − 6 > 0.

Exempel. Visa att 6 är en delare till alla heltal på formen 8^{n} − 2^{n}, för n ∈ ℤ^{+}. (1) Satsen är sant för n = 1 eftersom 6|8 − 2.

(2) Antag att 6|8^{n} − 2^{n} för alla n ≤ k. Vi ska visa att 6|8^{k+1} − 2^{k+1}. På grund av induktionsantagandet är 8^{k} − 2^{k} = 6h där h ∈ ℤ. Det följer att:

8^{k+1} = 8·8^{k} = 8(2^{k} +6h) = (2+6)(2^{k} +6h) = 2(2^{k} +6h)+6(2^{k} +6h) = 2^{k+1} +6(18h+2^{k})

Så 8^{k+1} − 2^{k+1} = 6(18h + 2^{k}) som betyder att 6|8^{k+1} − 2^{k+1}

övning

(1) Räkna upp elementen av Fibonacciföljden.

(2) Visa, med hjälp av induktion, att n! > 2^{n} för n ≥ 4.

(3) Visa att

∑_{i=n}^{2n−1}(2i + 1) = 3n^{2} för alla n ∈ ℤ^{+}