Diskret matematik: Matematisk induktion - Visa att följande uttryck gäller för alla n ≥ 0

Hej!

Undrar om en till induktionsbevis fråga.

• Visa att ($\sum _{k=0}^{n}4 * 5^k=5^{n+1}-1$) gäller för alla heltal n ≥  0. 

Lösning: 

1. Bassteg: visa att uttrycket gäller då n = 0: 

HL = $4 * 5^0 = 4$

VL = $5^{0+1} - 1 = 4$

Nu vet vi att HL = VL, OK!

2. Antagande: antag att uttrycket gäller då n = m ≥  0:

$\sum _{k=0}^{m}4 * 5^k=5^{m+1}-1$

3. Visa med hjälp av antagandet i steg 2 att uttrycket gäller även för n = m + 1 ≥ 0 

$\sum _{k=0}^{m+1}4 * 5^k=5^{(m+1)+1}-1$

Vår HL = $5^{m+2}-1$

Nu vill vi visa att VL är också samma som HL

VL = $\sum _{k=0}^{m+1}4 * 5^k = \sum _{k=0}^{m}4 * 5^k +\sum _{k=0}^{ m+1}4 * 5^k$

Vi vet ju att ($\sum _{k=0}^{m}4 * 5^k = 5^{m+1}-1$) från antagandet i steg 2 och då kan vi ersätta det i vår VL:

VL = $\sum _{k=0}^{m+1}4 * 5^k = \mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{m}}\mathbf{4}\mathbf{ }\mathbf{*}\mathbf{ }{\mathbf{5}}^{\mathbf{k}} +\sum _{k=0}^{ m+1}4 * 5^k$

VL = $\sum _{k=0}^{m+1}4 * 5^k = \mathbf{(}{\mathbf{5}}^{\mathbf{m}\mathbf{+}\mathbf{1}}\mathbf{-}\mathbf{1}\mathbf{)} +\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{ }\mathbf{m}\mathbf{+}\mathbf{1}}\mathbf{4}\mathbf{ }\mathbf{*}\mathbf{ }{\mathbf{5}}^{\mathbf{k}}$

Nu vill jag fortsätta räkna den andra summan(summan i grön färg), enligt min förståelse så vill jag nu ersätta k mot m+1:
VL = $\sum _{k=0}^{m+1}4 * 5^k = \mathbf{(}{\mathbf{5}}^{\mathbf{m}\mathbf{+}\mathbf{1}}\mathbf{-}\mathbf{1}\mathbf{)} +\mathbf{(}\mathbf{4}\mathbf{ }\mathbf{*}\mathbf{ }{\mathbf{5}}^{\mathbf{m}\mathbf{+}\mathbf{1}}\mathbf{)}$

Nu tänkte jag att man kan fortsätta på detta sättet:

$\sum _{k=0}^{m+1}4 * 5^k = {\mathbf{5}}^{\mathbf{m}\mathbf{+}\mathbf{1}} +\mathbf{4}\mathbf{ }\mathbf{*}\mathbf{ }{\mathbf{5}}^{\mathbf{m}\mathbf{+}\mathbf{1}}\mathbf{-}\mathbf{1}$

$\sum _{k=0}^{m+1}4 * 5^k =5 * 5^{m+1}-1$

Det blir dock fel och jag lyckas inte visa att vänsterledet är lika med högerledet. Jag fattar inte vad jag gör för fel, det är alltid i steg 3 jag har problem.... Hoppas att min presentation av lösningen är tydlig och tack i förhand!