Extra Credit Problems, Assigned August 24, 2005

Due September 7, 2005

You may work in groups if you wish, but please make sure
that you report with whom you work.  Points will be
divided among the group members, and rounded up.
Please do not consult outside sources, including the Internet
and books.  The one exception is the text.  If you consult
your text, please let me know, and I will charge one point
for having used the text on that problem.

On all problems, correct answers are worth 0 points, but
correct explanations and answers receive full credit.  Partial
credit is given for partial solutions.

1.  [5 points]  How many ways are there to walk from A to
B on the figure to the right, walking only North, East or Northeast
on each step?  One such way is E, NE, E, N, N.

2.  [7 points]  How many anagrams are there of the letters of the word
"REPEATER"?  Here, "anagram" means any arrangement of
the letters, whether it yields a sensible word or not.  An
alphabetical list of the anagrams would begin like this:
AEEEPRRT, AEEEPRTR, AEEEPTRR, AEEERPRT, ...

3.  [8 points]  How many distinct binary trees are there on the leaves A, B, C, D, E?
If there were just three leaves instead of five, the answer would
be "3," with the three distinct trees shown below.


One of the trees on five vertices is shown to the right.  What
characterizes a binary tree is that each internal node has exactly
two nodes (leaves or other non-leaf nodes) below it.

4.  [10 points]  The Fibonacci numbers are the sequence 1, 1, 2, 3, 5, 8, 13, ....
In this sequence, each number is the sum of the two previous
numbers.  We designate these numbers as follows:
F₀ = 1, F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5, F₅ = 8, etc...
and F_n = F_n-1 + F_n-2.
   a.  Find a formula for the sum F₀ + F₁ + ... + F_n
   b.  Prove that your formula is correct.
By "prove," I mean "provide a convincing argument."