Die Fibonacci-Zahlen ´F_n, n in NN_0´, sind definiert durch ´F_0 = 0´, ´F_1 = 1´, ´F_(n+2) = F_n + F_(n+1)´.

Zeige mit Hilfe der vollständigen Induktion die folgende Beziehung:

´sum_(k=0)^n F_(2k+1) = F_(2n+2)´

Solution
  • Sei ´p(n) := sum_(k=0)^n F_(2k+1) = F_(2n+2)´ mit ´Fn:´ Fibonacci- Zahl von ´n´.

    Zu zeigen : ´AAn in NN : p(n)´

    Induktionsbasis:

    Sei ´n = 0´, zu Zeigen: ´p(0)´ ist wahr. ´sum_(k=0)^0 F_(2k+1) = F_1 = F_2 = F_(2 * 0+2)´

    Induktionsschritt:

    Zu zeigen: ´AA n in NN : p(n) => p(n + 1)´ Sei ´n in N´ beliebig aber fest.

    ´p(n)´ ´=> sum_(k=0)^n F_(2k+1) = F_(2n+2)´ ´| +F_(2(n+1)+1)´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2(n+1)+1) + F_(2n+2)´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2n+2) + F_(2n+3)´ ´|"Definition" Fib´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2n+4)´ ´|"Defintion" Sigma´ ´=> sum_(k=0)^(n+1) F_(2k+1) = F_(2(n+1)+2)´ ´=> p(n+1)´

    Aus der Induktionsbasis und dem Induktionsschritt folgt die Korrektheit von ´p(n)´ für alle ´n in N´.

  • URL:
  • Language:
  • Subjects: math
  • Type: Proof
  • Duration: 35min
  • Credits: 6
  • Difficulty: 0.5
  • Tags: hpi proof fibonacci induction
  • Note:
    HPI, Mathematik I - Diskrete Strukturen und Logik, WS 2012/2013, Nr. 32a
  • Created By: adius
  • Created At:
    2013-04-12 16:49:14 UTC
  • Last Modified:
    2014-07-21 05:00:36 UTC