Rekursive Abbild Beweis

Question

Die Abbildung g : IN0 → Z sei rekursiv definiert durch

g(0) = 3 und g(n + 1) = g(n) + 4n − 3 fur alle n ≥ 0.

Entscheiden Sie, welche der folgenden Aussagen wahr ist/sind und welche falsch. Beweisen

Sie dazu die Aussage oder geben Sie ein Gegenbeispiel an.

(a) g(n) = n ^2− 4n + 3 fur alle n ∈ IN0.

(b) g(n) = 2n^2 − 5n + 3 fur alle n ∈ IN0.

Kann mir jemand bei der Aufgabe erklären, wie ich vorgehen soll?

Danke.

Answer 1

mach einfach induktion

linke Seite         rechte Seite

n=0

g(0)=3              g(0)=0^2 - 4*0 +3 = 0-0+3 = 3  IA passt

n => n +1

Ziel: g(n+1) = (n+1)^2 - 4 * (n+1) +3 = n^2 + 2n +1 -4n-4 +1 = n^2 - 2n

g(n+1) = g(n) +4n-3 = n^2-4n+3+4n-3 = n^2    => Beweis gilt nicht 

nicht ganz so formal aber müsste ein Ansatz sein (gegenbeispiel z.B für n="

die b ist analog nur das dort der Beweis stimmt