Discrete Mathematics: Elementary and Beyond

3.6 Identities in Pascal’s Triangle 51 +···+(−1)n−^1 [( n− 1 n− 2 ) + ( n− 1 n− 1 )] +(−1)n ( n− 1 n− 1 ) , which is clearly 0, ...

52 3. Binomial Coefficients and Pascal’s Triangle We will give an interpretation of both sides of the identity as the result of ...

3.6 Identities in Pascal’s Triangle 53 Here is another relation between the numbers in Pascal’s Triangle. Let us start with the ...

54 3. Binomial Coefficients and Pascal’s Triangle 3.6.4Suppose that you want to choose a (k+1)-element subset of the (n+k+1)- el ...

3.7 A Bird’s-Eye View of Pascal’s Triangle 55 3.7.1For which values ofnandkis
n k+1  twice the previous entry in Pascal’s Tria ...

56 3. Binomial Coefficients and Pascal’s Triangle nis even, then we already know that the largest entry in thenth row is the mid ...

3.8 An Eagle’s-Eye View: Fine Details 57 fast do they drop? Figure 3.4 suggests that starting from the middle, the binomial coef ...

58 3. Binomial Coefficients and Pascal’s Triangle (^020406080100) 1029 (^020406080100) 1029 FIGURE 3.5. The Gauss curvee−t (^2) ...

3.8 An Eagle’s-Eye View: Fine Details 59 So we have some sort of a formula for this ratio, but how useful is it? How do we tell, ...

60 3. Binomial Coefficients and Pascal’s Triangle Remember, this is an upper bound on the logarithm of the ratio ( 2 n m )/( 2 m ...

3.8 An Eagle’s-Eye View: Fine Details 61 Lemma 3.8.2Let 0 ≤k≤mandc= ( 2 m k )/( 2 m m ) . Then ( 2 m 0 ) + ( 2 m 1 ) +···+ ( 2 m ...

62 3. Binomial Coefficients and Pascal’s Triangle oftadds up to less thancA, the next block to less thanc^2 A, etc. Adding up, w ...

3.8 An Eagle’s-Eye View: Fine Details 63 3.8.6In city with a regular “chessboard” street plan, the North-South streets are calle ...

64 3. Binomial Coefficients and Pascal’s Triangle 3.8.14Letnbe a positive integer divisible by 3. Use Stirling’s formula to find ...

4 Fibonacci Numbers 4.1 Fibonacci’s Exercise In the thirteenth century, the Italian mathematician Leonardo Fibonacci studied the ...

66 4. Fibonacci Numbers rabbits are added. This means that the farmer will have 5 rabbits during the fifth month. It is easy to ...

4.1 Fibonacci’s Exercise 67 Forn= 1, there is only 1 way. Forn= 2, you have 2 choices: take one step twice or two once. Forn= 3, ...

68 4. Fibonacci Numbers 4.2 Lots of Identities There are many interesting relations valid for the Fibonacci numbers. For example ...

4.2 Lots of Identities 69 (c) F 02 +F 12 +F 22 +···+Fn^2 =Fn·Fn+1. (d) Fn− 1 Fn+1−Fn^2 =(−1)n. 4.2.4We want to extend the Fibona ...

70 4. Fibonacci Numbers Wait a minute! What kind of trickery is this? We use (4.3) in the proof of (4.2), and then (4.2) in the ...