1

A path consists of vertical and horizontal line segments of length 1. Determine the number of paths

1. of length 7 from the origin \(\left( 0,0 \right)\) and \((4,3)\) .

2. of length \(a + b\) from \(\left( 0,0 \right)\) and \((a,b)\) .

2

A lattice point in the plane is a point \((m,n)\) with \(m,n \in \Z\text{.}\)

1. How many paths of length 4 are there from \((0,0)\) to lattice points on the line \(y = - x + 4\) ?

2. Determine the number of paths of length 10 from \((0,0)\) to the lattice points on \(y = 10 - x\) .

3

Give a geometrical (path argument) for the identity \(2^{n} = \binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}\) using the idea in Exercise A.1.2.

4

Generalize Exercise A.1.1 to three dimensions; introduce obstructions; use inclusion-exclusion.

5

Give a path proof for \(\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}\) .

6

How many lattice paths from \(\left( 0,0 \right)\) to all lattice points on the line \(x + 2y = n\) are there?

7

Determine the number of lattice paths from \(\left( 0,0,0 \right)\) to lattice points on that portion of the plane \(x + y + z = 2\) that lies in the first octant.

8

Generalize Exercise A.1.7.

9

Determine the number of lattice paths from \(\left( 0,0 \right)\) to \((n,n)\) that do not cross over (they may touch) the line \(y = x\text{.}\)

1

Give a geometric interpretation for \(T_{n} + T_{n + 1} = \left( n + 1 \right)^{2}.\)

2

Verify that \(T_{n} + T_{m} + mn = T_{m + n}\) algebraically.

3

Give a geometric interpretation of the formula in Problem 2.

4

Verify that \(T_{n}^{2} + T_{n - 1}^{2} = T_{n^{2}}\) .

5

Verify the following:

1. \(3T_{n} + T_{n + 1} = T_{2n + 1}\)

2. \(3T_{n} + T_{n - 1} = T_{2n}\) (also give a geometrical proof)

6

Determine the values \(T_{6},T_{66},T_{666},T_{6666},\ldots\) . Make a general statement and prove it.

7

Determine the formula for \(T_{3} + T_{6} + T_{9} + \ldots + T_{3n}.\)

8

Verify:

1. \(1 + 3 + 6 + 10 + 15 = 1^{2} + 3^{2} + 5^{2}\)

2. \(1 + 3 + 6 + 10 + 15 + 21 = 2^{2} + 4^{2} + 6^{2}\)

3. Generalize and prove your generalization.

1

Briefly address history.

2

Using a variety of proof methods (geometric, induction, matrices, recursion, telescoping sum) prove identities such as:

1. \(F_{1} + F_{2} + \ldots + F_{n} = F_{n + 2} - 1\)

2. \(F_{1}^{2} + F_{2}^{2} + \ldots + F_{n}^{2} = F_{n}F_{n + 1}\)

3. \(F_{n + 1}^{2} - F_{n}F_{n + 2} = \left( - 1 \right)^{n}\)

4. \(F_{n + 2} = \binom{n + 1}{0} + \binom{n}{1} + \binom{n - 1}{2} + \cdots\)

3

Prove the “Binet Formula,” \(F_{n} = \frac{\alpha^{n} - \beta^{n}}{\alpha - \beta}\) , where \(\alpha,\beta\) satisfy \(x^{2} - x - 1 = 0\) .

1. By induction.

2. Using generating series.

4

Use the Binet Formula to prove,

5

Investigate the geometric interpretations of the \(F_{n}\) .

6

Prove that,

7

Let \(Q =\begin{pmatrix}1 \amp 1 \\ 1 \amp 0\end{pmatrix}\) . Prove:

1. \(Q^{n} = \begin{pmatrix} F_{n + 1} \amp F_{n}\\ F_{n} \amp F_{n - 1} \end{pmatrix}\) .

2. \(Q^{2} = Q + I\text{;}\) use \(Q^{2n}\) to prove the identity in Problem 4.

3. Use \(Q^{2n + 1} = Q^{n}Q^{n + 1}\) to show \(F_{2n + 1} = F_{n + 1}^{2} - F_{n}^{2}\) and other identities.

8

Show that if \(x^{2} = x + 1\) then \(x^{n} = F_{n}x + F_{n - 1}\) for \(n \geq 2\) . Use this result to prove the Binet Formula, namely that \(F_{n} = \frac{\alpha^{n} - \beta^{n}}{\alpha - \beta}\) .

9

Investigate Lucas, Tribonacci, Tetranacci numbers.

1

Expand \({\left( 1 + x + x^{2} \right)}^{2}\text{,}\) \(\left( 1 + x + x^{2} \right)^{3}\text{,}\) and \(\left( 1 + x + x^{2} \right)^{4}\text{.}\)

2

Organize the coefficients as in the following triangle:

3

Investigate the properties of this triangle:

1. Produce the next row.

2. Give a recursion that produces elements in this triangle.

3. What are the row sums? Prove it!

4. What is the sum \(1^{2} + 2^{2} + 3^{2} + 2^{2} + 1^{2}\) ? Generalize and prove.

5. Is there a hockey stick theorem?

4

Investigate 3-dimensional versions of \(\left( 1 + x + x^{2} \right)^{n}\) and \(\left( x + y + z \right)^{n}.\)

5

Investigate \(\left( 1 + x + x^{2} + x^{3} \right)^{n}\) .

6

Investigate \(\left( 1 + x + x^{2} + \ldots + x^{k} \right)^{n}\) .

7

Where do the “Fibonacci” numbers get involved in the Pascal triangle?

8

Where do the “Tribonacci” numbers appear in the triangle in Problem 2?

1

Show algebraically and geometrically that \(\binom{n}{2} + \binom{n + 1}{2} = n^{2}\) .

2

Show that \(\binom{n}{3} + 4 \binom{n + 1}{3} + \binom{n + 2}{3} = n^{3}\) .

3

Use Problem 1 and the hockey stick theorem to find a nice formula for \(1^{2} + 2^{2} + 3^{2} + \ldots + n^{2}\) . Contrast with the version usually seen in calculus.

4

Use Problem 2 to find a nice formula for \(1^{3} + 2^{3} + 3^{3} + \ldots + n^{3}\) .

5

Express \(n^{4}\) as in Problems 1 and 2.

6

Use Problem 5 to find a nice formula for \(1^{4} + 2^{4} + 3^{4} + \ldots + n^{4}\) .

7

Here is an alternate way of accomplishing Problem 6: Find integers \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\) so that

using \(n=1, 2, 3, 4\text{.}\) This sometimes referred to as “Polynomial Fitting.”

8

Express \(n^{3}\) as in Problems 1 and 2.

9

Express \(1^{5} + 2^{5} + 3^{5} + \ldots + n^{5}\) as a sum of multiples of binomial coefficients.

10

In Problems 1, 2, 5, and 7, \(n^{2},n^{3},n^{4},\) and \(n^{5}\) were expressed as sums of binomial coefficients with integer coefficients. Arrange these expressions in a Pascal-like triangle, concentrating on these integer coefficients. The coefficients are called Eulerian numbers.

11

Investigate the properties of this triangle. Include a discussion of row sums, how entries are found, and a possible recursion. Use \(\begin{bmatrix} n\\ k \end{bmatrix}\) for notation.

1

State the rule used to form each entry, and produce the next two rows.

2

What are the “initial conditions” needed to generate the entries?

3

Use \(\begin{bmatrix} n\\ k \end{bmatrix}\) as the notation for entries and state properties analogous to those found in the Pascal Triangle. Include closed formulas for each entry, row sums (alternating also), hockey stick theorem, hexagon property, sum of squares of row entries, etc. Indicate how partial fractions help in verifying the (infinite) hockey stick theorem.

4

See if you can find any papers on this topic. Check Pi Mu Epsilon Journal, The Mathematical Gazette, Mathematics Magazine, Delta-Undergraduate Mathematics Journal, etc.

1

Make the next few rows.

2

Where have you seen this triangle before?

3

Experiment with factoring each integer in the 6th row. Repeat with other rows.

4

What are the entries in row 12?

5

Where does the expression \(1 \cdot n + 2\left( n - 1 \right) + 3\left( n - 2 \right) + \cdots + n \cdot 1\) show up in the triangle?

6

Explain why \(1 \cdot n + 2\left( n - 1 \right) + 3\left( n - 2 \right) + \cdots + n \cdot 1 = \binom{n + 2}{3}\) .