heureka

avatar
Usernameheureka
Score26367
Membership
Stats
Questions 17
Answers 5678

 #4
avatar+26367 
+9

Hello CPhill !

 

My attempt:

 

EXAMPLE
Triangle starts

1

1    2

1    4    6

1    6   16   22

1    8   30   68   90

1   10   48  146  304  394

1   12   70  264  714 1412 1806

 

A033877:
Triangular array read by rows associated with Schroeder numbers:
T(1,k) = 1;
T(n,k) = 0, if k T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k).
1,
1, 2,
1, 4, 6,
1, 6, 16, 22,
1, 8, 30, 68, 90,
1, 10, 48, 146, 304, 394,
1, 12, 70, 264, 714, 1412, 1806,
1, 14, 96, 430, 1408, 3534, 6752, 8558,
1, 16, 126, 652, 2490, 7432, 17718, 33028, 41586,
1, 18, 160, 938, 4080, 14002, 39152, 89898, 164512, 206098

Note that for the terms T(n,k) of this triangle n indicates the column and k the row.

Source: https://oeis.org/search?q=A033877


Consider a Pascal triangle variant where T(n, k) = T(n, k-1) + T(n-1, k-1) + T(n-1, k), i.e.,
the order of performing the calculation must go from left to right (A033877).
This sequence is the rightmost diagonal.

Triangle begins:

  1;

  1,  2;

  1,  4,  6;

  1,  6, 16, 22;

  1,  8, 30, 68, 90;

(End)

A006318:
Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).
    1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738,
142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926,
3236724317174, 17518619320890, 95149655201962, 518431875418926,
2832923350929742, 15521467648875090

 

Formula Large Schröder numbers:
\(\text{For $n > 0 $, $ \\ \displaystyle a(n) = \left(\dfrac{1}{n}\right)* \sum \limits_{k=0}^n \Big(2^k*C(n, k)*C(n, k-1) \Big) $ .}\)

Source: https://oeis.org/A006318

 

The routes from A to J:  

\(n=3:\)

\(\begin{array}{|rcll|} \hline a(3) &=& \dfrac13 * \Big( 2^0 * C(3,0) * C(3,-1) \\ && + 2^1 * C(3,1) * C(3,0) \\ && + 2^2 * C(3,2) * C(3,1) \\ && + 2^3 * C(3,3) * C(3,2) \Big) \\ a(3) &=& \dfrac13 * \Big( 1*1*0+ 2 * 3 * 1 + 4 * 3 * 3 + 8 * 1 * 3 \Big) \\ a(3) &=& \dfrac13 * \left( 0 + 6 + 36 + 24 \right) \\ \mathbf{a(3)} & \mathbf{=} & \mathbf{22} \\ \hline \end{array} \)

 

laugh

Nov 26, 2018
 #1
avatar+26367 
+10

Wie löse ich diese Induktion bzw. wie bekomme ich den Induktionsschritt hin .

 

\(\bf{\text{Zeigen Sie mit vollständiger Induktion:}} \\ \displaystyle \sum\limits_{k=1}^{2n} \dfrac{ (-1)^{k-1} } { k } =\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k }, \text{ für alle } n \in \mathbb{N} \)

 

\(\text{Induktionsanfang:} \\ \begin{array}{|lll|} \hline n=1 & \text{linke Seite:} & \sum\limits_{k=1}^{2} \dfrac{ (-1)^{k-1} } { k }\\ & &= \dfrac{(-1)^0}{1} +\dfrac{(-1)^1}{2} \\ & &= 1- \dfrac12 \\ & &\mathbf{= \dfrac12} \\\\ & \text{rechte Seite:} & \sum\limits_{k=1}^{1} \dfrac{ 1 } { 1+k } \\ & &= \dfrac{1}{1+1} \\ & &\mathbf{= \dfrac12} \\ \hline \end{array}\)

 

\(\text{Für $\mathbf{n=1}$ sind beide Seiten gleich, und die Aussage ist wahr!}\)

 

\(\text{Die Induktionsannahme (I.A.) lautet:} \\ \begin{array}{|rcll|} \hline \displaystyle \sum\limits_{k=1}^{2n} \dfrac{ (-1)^{k-1} } { k } &=& \displaystyle \sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } \\ \hline \end{array}\)

 

\(\text{Der Induktionsschluss von $\mathbf{n}$ nach $\mathbf{n+1}$:} \\ \begin{array}{|rcll|} \hline \displaystyle \sum\limits_{k=1}^{2(n+1)} \dfrac{ (-1)^{k-1} } { k } &=&\displaystyle \sum\limits_{k=1}^{n+1} \dfrac{ 1 } { (n+1)+k } \\ \hline \end{array}\)

 

\(\bf{\text{linke Seite:}} \\ \begin{array}{|rcll|} \hline \mathbf{ \displaystyle \sum\limits_{k=1}^{2(n+1)} \dfrac{ (-1)^{k-1} } { k } } \\ &= & \displaystyle \sum\limits_{k=1}^{2n+2} \dfrac{ (-1)^{k-1} } { k } \\\\ &= & \displaystyle \sum\limits_{k=1}^{2n} \dfrac{ (-1)^{k-1} } { k } + \overbrace{\dfrac{(-1)^{(2n+1)-1} }{2n+1}}^{\text{für }k=2n+1\text{ :}} + \overbrace{\dfrac{(-1)^{(2n+2)-1} }{2n+2}}^{\text{für }k=2n+2\text{ :}} \\\\ &= & \displaystyle \sum\limits_{k=1}^{2n} \dfrac{ (-1)^{k-1} } { k } + \overbrace{\dfrac{(-1)^{2n} }{2n+1}}^{\text{Exponent gerade :}} + \overbrace{\dfrac{(-1)^{2n+1} }{2n+2}}^{\text{Exponent ungerade :}} \\\\ &= & \displaystyle \sum\limits_{k=1}^{2n} \dfrac{ (-1)^{k-1} } { k } + \dfrac{ 1 }{2n+1} - \dfrac{ 1 }{2n+2} \\\\ &\mathbf{\overset{I.A.}{=}} & \mathbf{ \displaystyle \sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{ 1 }{2n+1} - \dfrac{ 1 }{2n+2} } \\ \hline \end{array}\)

 

\(\small{ \bf{\text{rechte Seite Vorbereitung :}} \\ \begin{array}{|ll|} \hline \sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } &=& \dfrac{1} {n+1} +& \dfrac{1} {n+2}+ \dfrac{1} {n+3}+ \ldots +\dfrac{1} {2n} \\ \sum\limits_{k=1}^{n+1} \dfrac{ 1 } { (n+1)+k } &=& & \dfrac{1} {n+2} + \dfrac{1} {n+3}+ \ldots +\dfrac{1} {2n}+\dfrac{1} {2n+1}+\dfrac{1} {2n+2} \\ \hline \sum\limits_{k=1}^{n+1} \dfrac{ 1 } { (n+1)+k } - \sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } &=& & \dfrac{1} {2n+1}+\dfrac{1} {2n+2} - \dfrac{1} {n+1} \\ \mathbf{ \sum\limits_{k=1}^{n+1} \dfrac{ 1 } { (n+1)+k } } &=& \mathbf{ \sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } +} & \mathbf{ \dfrac{1} {2n+1}+\dfrac{1} {2n+2} - \dfrac{1} {n+1} } \\ \hline \end{array} }\)

 

\(\bf{\text{rechte Seite:}} \\ \begin{array}{|ll|} \hline \mathbf{ \displaystyle\sum\limits_{k=1}^{n+1} \dfrac{ 1 } { (n+1)+k } } &=& \mathbf{ \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1}+\dfrac{1} {2n+2} - \dfrac{1} {n+1} } \\\\ &=& \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1}+\dfrac{1} {2(n+1)} - \dfrac{1} {n+1} \\\\ &=& \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1} - \dfrac{1} {n+1} \cdot \left(1-\dfrac12 \right) \\\\ &=& \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1} - \dfrac{1} {n+1} \cdot \left(\dfrac12 \right) \\\\ &=& \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1} - \dfrac{1} {2(n+1)} \\\\ &\mathbf{=}&\mathbf{ \displaystyle\sum\limits_{k=1}^{n} \dfrac{ 1 } { n+k } + \dfrac{1} {2n+1} - \dfrac{1} {2n+2} } \\ \hline \end{array}\)

 

laugh

Nov 22, 2018