heureka

avatar
Usernameheureka
Score26367
Membership
Stats
Questions 17
Answers 5678

 #1
avatar+26367 
+1

Beweisen Sie mit Hilfe der vollständigen Induktion folgende Aussage für alle natürlichen Zahlen n:
\huge{\sum \limits_{i=1}^{n} \frac{i}{2^i}=2-\frac{n+2}{2^n}}

\(\huge{\sum \limits_{i=1}^{n} \frac{i}{2^i}=2-\frac{n+2}{2^n}} \)

 

Induktionsanfang:

n = 1:    linke Seite: \(\dfrac{1}{2^1 } = \dfrac{1}{2}\)
          rechte Seite:  \(2-\dfrac{1+2}{2^1} = 2-\dfrac{3}{2} = \dfrac{1}{2}\)
Für n=1 sind beide Seiten gleich!

 

Die Induktionsannahme (I.A.) lautet:
\( \displaystyle \sum \limits_{i=1}^{n} \frac{i}{2^i}=2-\frac{n+2}{2^n}\)

 

Induktionsbehauptung:

\(\displaystyle \sum \limits_{i=1}^{n+1} \frac{i}{2^i}=2-\frac{(n+1)+2}{2^{n+1}}\)

 

Beweis des Induktionsschritts \(n\rightarrow n+1:\)

\(\begin{array}{|lrcll|} \hline n+1:\\ \text{linke Seite:} \\ && & \displaystyle \sum \limits_{i=1}^{n+1} \frac{i}{2^i} \\\\ &&=& \displaystyle \sum \limits_{i=1}^{n} \frac{i}{2^i} + \dfrac{n+1}{2^{n+1}} \\\\ &&\overset{I.A.}{=}& \displaystyle 2-\frac{n+2}{2^n} + \dfrac{n+1}{2^{n+1}} \\\\ &&=& \displaystyle 2- \left( \frac{n+2}{2^n} - \dfrac{n+1}{2^{n+1}} \right) \\\\ &&=& \displaystyle 2- \left[ \frac{n+2}{2^n}\cdot\left(\dfrac{2}{2}\right) - \dfrac{n+1}{2^{n+1}} \right] \\\\ &&=& \displaystyle 2- \left( \frac{(n+2)\cdot 2}{2^n\cdot 2} - \dfrac{n+1}{2^{n+1}} \right) \\\\ &&=& \displaystyle 2- \left( \frac{(n+2)\cdot 2}{2^{n+1}} - \dfrac{n+1}{2^{n+1}} \right) \\\\ &&=& \displaystyle 2- \frac{(n+2)\cdot 2-(n+1)}{2^{n+1}} \\\\ &&=& \displaystyle 2- \frac{2n+4-n-1} {2^{n+1}} \\\\ &&=& \displaystyle 2- \frac{n+3}{2^{n+1}} \\\\ &&=& \displaystyle 2- \frac{(n+1)+2}{2^{n+1}} \\\\ \text{rechte Seite:} \\ &&& \displaystyle 2-\frac{(n+1)+2}{2^{n+1}} \\\\ \text{Ergebnis:}\\ && & \displaystyle 2- \frac{(n+1)+2}{2^{n+1}} = 2-\frac{(n+1)+2}{2^{n+1}}\ \checkmark \\ \hline \end{array}\)

 

 

laugh

Mar 23, 2018
 #1
avatar+26367 
+3

The Fibonacci sequence, with \(F_0 = 0\), \(F_1 = 1\) and \(F_n = F_{n - 2} + F_{n - 1}\), had a closed form \(F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \widehat{\phi}^n \right),\) where \(\phi = \frac{1 + \sqrt{5}}{2} \; \text{and} \; \widehat{\phi} = \frac{1 - \sqrt{5}}{2}.\) The Lucas numbers are defined in a similar way. Let \(L_0\) be the zeroth Lucas number and \(L_1\) be the first. If \(\begin{align*} L_0 &= 2 \\ L_1 &= 1 \\ L_n &= L_{n - 1} + L_{n - 2} \; \text{for}\; n \geq 2 \end{align*}\) Find \((a,b)\) such that \(L_n = a\phi^n + b\widehat{\phi}^n.\)

 

 

\(\text{Fibonacci sequence $0,1,1,2,3,5,8,13,21,34,55,\ldots$} \\ \begin{array}{|lcr|} \hline a_0 = a_0 &=& 0\cdot a_1 + 1 \cdot a_0 \\ a_1 = a_1 &=& 1\cdot a_1 + 0 \cdot a_0 \\ a_2 = a_1+a_0 &=& 1\cdot a_1 + 1 \cdot a_0 \\ a_3 = a_2+a_1 &=& 2\cdot a_1 + 1 \cdot a_0 \\ a_4 = a_3+a_2 &=& 3\cdot a_1 + 2 \cdot a_0 \\ a_5 = a_4+a_3 &=& 5\cdot a_1 + 3 \cdot a_0 \\ a_6 = a_5+a_4 &=& 8\cdot a_1 + 5 \cdot a_0 \\ a_7 = a_6+a_5 &=& 13\cdot a_1 + 8 \cdot a_0 \\ a_8 = a_7+a_6 &=& 21\cdot a_1 + 13 \cdot a_0 \\ \ldots \\ a_n = a_{n-1}+a_{n-2} &=& F_n\cdot a_1 + F_{n-1} \cdot a_0 \\ && \boxed{a_n = F_n\cdot a_1 + F_{n-1} \cdot a_0 } \\\\ \text{Lucas numbers:} \\ a_0 = L_0 = 2 \\ a_1 = L_1 = 1 \\ a_n = L_n =F_n\cdot 1 + F_{n-1} \cdot 2 \\ && \boxed{L_n =F_n + 2F_{n-1}} \\ \hline \end{array} \)

 

\(\begin{array}{|rcll|} \hline F_n &=& \frac{1}{\sqrt{5}} \left( \phi^n - \widehat{\phi}^n \right) \\ F_{n-1} &=& \frac{1}{\sqrt{5}} \left( \phi^{n-1} - \widehat{\phi}^{n-1} \right) \\ \boxed{L_n =F_n + 2F_{n-1}} \\ L_n &=& \frac{1}{\sqrt{5}} \left( \phi^n - \widehat{\phi}^n \right) + 2\frac{1}{\sqrt{5}} \left( \phi^{n-1} - \widehat{\phi}^{n-1} \right) \\ &=& \dfrac{ \left( \phi^n - \widehat{\phi}^n \right)+2\left( \phi^{n-1} - \widehat{\phi}^{n-1} \right) } { \sqrt{5} } \\ &=& \dfrac{ \phi^n - \widehat{\phi}^n+2 \phi^{n-1} - 2\widehat{\phi}^{n-1} } { \sqrt{5} } \\ &=& \dfrac{ \phi^n+2 \phi^{n-1} - \widehat{\phi}^n - 2\widehat{\phi}^{n-1} } { \sqrt{5} } \\ &=& \dfrac{ \phi^n\left( 1+\dfrac{2}{\phi} \right) - \widehat{\phi}^n\left( 1+\dfrac{2}{\widehat{\phi}} \right) }{ \sqrt{5} } \quad | \quad \frac{1}{\phi} = \phi -1 \quad \frac{1}{\widehat{\phi}} = \widehat{\phi} -1 \\ &=& \dfrac{ \phi^n\Big( 1+2(\phi -1 ) \Big) - \widehat{\phi}^n\left( 1+2(\widehat{\phi} -1) \right) }{ \sqrt{5} } \\ &=& \dfrac{ \phi^n( 2\phi -1 ) - \widehat{\phi}^n\left( 2\widehat{\phi} -1 \right) }{ \sqrt{5} } \quad | \quad 2\phi -1 = \sqrt{5} \quad 2\widehat{\phi} -1= -\sqrt{5} \\ &=& \dfrac{ \phi^n\sqrt{5} - \widehat{\phi}^n\left( -\sqrt{5} \right) }{ \sqrt{5} } \\ &=& \dfrac{ \phi^n\sqrt{5} + \widehat{\phi}^n \sqrt{5} } { \sqrt{5} } \\ &=& \phi^n + \widehat{\phi}^n \\ \boxed{L_n =\phi^n + \widehat{\phi}^n } \\ \hline \end{array}\)

 

(a,b) = (1,1)
 

laugh

Mar 21, 2018
 #1