SOLUTIONS

No problem is ever permanently closed. Any comments, new solutions, or new insights on old problems are always welcomed by the problem editor.

93. [1996, 89] Proposed by Alan H. Rapoport, Ashford Medical Center, Santurce, Puerto Rico.

(a) What is the minimum number of people needed in order to assure a greater than 50% chance of at least three having the same birthday?

(b) What is the minimum number of people you must query in order to have a 50% chance of finding at least two having your birthday?

Solution by N. J. Kuenzi, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin.

(a) We can model this situation as an ordered random sample of size n with replacement from a finite population of N distinct objects. There are N^{n} equally likely outcomes in the sample space.

Let B denote the event that at least one object is selected three or more times in the sample. Then \overline{B} is the event that any item is selected at most twice. We will find an expression for P (\overline{B}).

Let A_{0} denote the event that all n objects selected in the sample are distinct. Then,

P (A_{0}) = \binom{N}{n}n!/N^{n}.

Let A_{1} be the event that exactly one object is selected twice and the other n−2 objects selected are distinct. Then there are \binom{N}{n−1} ways to select the n − 1 objects,

\binom{n−1}{1} ways to pick the “double”, and n!/2 ways to form an ordered arrangement. So,

P (A_{1}) = \binom{N}{n − 1}\binom{n − 1}{1}n!/(2N^{n}).

In general for j, 2 ≤ j ≤ n/2, let A_{j} denote the event that exactly j objects

are selected twice and the other n − 2j objects are distinct. Then there are \binom{N}{n−j} ways to choose the n−j items for the sample, \binom{n−j}{j} ways to select the j “doubles”,

and n!/2^{j} ways to form an ordered arrangement. So,

P (A_{j}) = \binom{N}{n − j}\binom{n − j}{j}n!/(2^{j}N^{n}).

Since A_{0}, A_{1}, …, A_{m} (where m is the greatest integer in n/2) partitions \overline{B}, we have

P (\overline{B}) = (n!/N^{n}) ∑_{j=0}^{m} \binom{N}{n − j}\binom{n − j}{j}/2^{j}.

With N = 365, a computer check yields

P (\overline{B}) > \frac{1}{2} for n ≤ 87 and P (\overline{B}) < \frac{1}{2} for n ≥ 88.

So 88 is the minimum number of people needed to assure a greater than 50% chance of at least three having the same birthday.

This result along with an equivalent expression for P (\overline{B}), attributed to C. F. Pinzka, is reported on page 830 of the October 1960 issue of the American Mathematical Monthly. Donald E. Knuth gives essentially the same expression for P (\overline{B}), on page 195 of the August-September 1977 issue of Crux Mathematicorum.

(b) We can model this problem as a sequence of independent Bernoulli trials with probability p of matching your birthday on each trial. The complement of at least two having your birthday is at most one of the n people matches your birthday.

Let \overline{B}_{n} denote the complement. Then

\begin{aligned}P (\overline{B}_{n}) & = q^{n} + npq^{n−1} \\ & = q^{n−1}(q + np) = q^{n−1}(1 + (n − 1)p), \end{aligned}

where q = 1 − p.

We can define P (\overline{B}_{n}) recursively as follows.

\begin{matrix}P (\overline{B}_{3}) = q^{2}(1 + 2p) \\ P (\overline{B}_{n+1}) = q(1 + np)P (\overline{B}_{n})/(q + np), for n ≥ 3. \end{matrix}

For a given p, compute P (\overline{B}_{n}) recursively until

P (\overline{B}_{n}) ≤ \frac{1}{2}.

Listed below is a brief program for the TI 80, TI 82, or TI 83.

Program  Comment
:Prompt P  input the probability p
:1 − P → Q  compute and store q
:Q^{2}(2P + 1) → S  compute P (\overline{B}_{3}) and store in S
:3 → N  initialize counter
:While (S > 0.5)  continue until P (\overline{B}_{n}) ≤ 0.5
:Q(1 + N ∗ P)S/(Q + N ∗ P) → S recursive formula
:N + 1 → N  increment counter
:End  end of the while loop
:Disp N  print out N and S.

:Disp S With p = 1/365, the output is n = 613 and P (\overline{B}_{n}) = 0.49936. For a February 29 leap year birthday, set p = 1/1461, the output is n = 2452

and P (\overline{B}_{n}) = 0.49994.

Comment by the proposer. The following is a list of references for the birthday problem.

\underline{References}

1. M. Abramson and W. O. J. Moser, “More Birthday Surprises,” American Mathematical Monthly, 77 (1970), 856–858.

2. J. D. Austin, “The Birthday Problem Revisited,” The Two-Year College Mathematics Journal, 7 (1976), 39–42.

3. T. Crilly and S. Nandy, “The Birthday Problem for Boys and Girls,” The Mathematical Gazette, 71 (1987), 19–22.

4. R. E. Greenwood and A. Richert, Jr. “A Birthday Holiday Problem,” Journal of Combinatorial Theory, 5 (1968), 422–424.

5. R. K. Guy, “Birthdays,” Nabla. Bull. Malayan Math. Soc., 9 (1962), 1–10.

6. R. L. Hocking and N. C. Schwertman, “An Extension of the Birthday Problem to Exactly k Matches,” College Mathematics Journal, 17 (1986), 315–321.

7. M. S. Klamkin and D. J. Newman, “Extensions of the Birthday Surprise,” Journal of Combinatorial Theory, 3 (1967), 278–282.

8. E. H. McKinney, “Generalized Birthday Problem,” American Mathematical Monthly, 73 (1966), 385–387.

9. F. Mosteller, “Understanding the Birthday Problem,” The Mathematics Teacher, 55 (1962), 322–325.

10. R. Pinkham, “The Birthday Problem; Pairs and Triples,” The Mathematical Gazette, 69, (1985), 279.

11 . R. S. Pinkham, “A Convenient Solution to the Birthday Problem for Girls

and Boys,” The Mathematical Gazette, 72 (1988), 129–130.

12. C. F. Pinzka, “Remarks on some Problems in the American Mathematical Monthly,” American Mathematical Monthly, 67 (1960), 830.

13. Solution to Problem 70.B, The Mathematical Gazette, 70 (1986), 228–229.

14. Solution to Problem 195, Crux Mathematicorum, 3 (1977), 83–87.

15. Solution to Problem 195, Crux Mathematicorum, 3 (1977), 195–196. Also solved by the proposer.

94. [1996, 90] Proposed by Curtis Cooper and Robert E. Kennedy, Central Missouri State University, Warrensburg, Missouri.

Let n be a nonnegative integer. Prove

∑_{k=0}^{n} \binom{n}{k}(−1)^{k}F_{k} = −F_{n},

where F_{n} denotes the nth Fibonacci number.

Solution I by Bob Prielipp, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Thomas C. Leong, The City College of City University of New York, New York, New York; James T. Bruening, Southeast Missouri State University, Cape Girardeau, Missouri; Joseph B. Dence, University of Missouri-St. Louis, St. Louis, Missouri; Russell Euler and Jawad Sadek, Northwest Missouri State University, Maryville, Missouri; Lawrence Somer, The Catholic University of America, Washington, D.C.; and Kenneth Davenport, Pittsburgh, Pennsylvania.

Our solution will use the Binet form for F_{j}:

F_{j} = \frac{α^{j} − β^{j}}{\sqrt{5}}

for each nonnegative integer j, where

α = \frac{1 + \sqrt{5}}{2} and β = \frac{1 − \sqrt{5}}{2}.

Note that α + β = 1 so 1 + (−α) = β and 1 + (−β) = α. Thus, by the Binomial Theorem,

\begin{aligned}∑_{k=0}^{n} \binom{n}{k}(−1)^{k}F_{k} & = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k} \frac{α^{k} − β^{k}}{\sqrt{5}} \\ & = \frac{1}{\sqrt{5}} ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}α^{k} − \frac{1}{\sqrt{5}} ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}β^{k} \end{aligned}

= \frac{1}{\sqrt{5}} ∑_{k=0}^{n} \binom{n}{k}1^{n−k}(−α)^{k} − \frac{1}{\sqrt{5}} ∑_{k=0}^{n} \binom{n}{k}1^{n−k}(−β)^{k}

= \frac{1}{\sqrt{5}}(1 + (−α))^{n} − \frac{1}{\sqrt{5}}(1 + (−β))^{n}

= \frac{1}{\sqrt{5}}β^{n} − \frac{1}{\sqrt{5}}α^{n}

= −\frac{α^{n} − β^{n}}{\sqrt{5}} = −F_{n}.

Solution II by the proposers.

Let f be a function such that f(n) = F_{n}. Also, use

F_{n} = F_{n−1} + F_{n−2}

to define F_{n} for all integers n. Now, each of the following can be proved by induction on n.

Let m and n be integers such that m, n ≥ 0. Then,

△^{n}f(m) = F_{m−n},

where

△f(x) = f(x + 1) − f(x).

Let n be an integer such that n ≥ 0. Then

(−1)^{n}F_{−n} = −F_{n}.

Let n be an integer such that n ≥ 0. Then

△^{n}f(x) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}f(x + k).

Using the first result with m = 0 and the last result with x = 0, we have

F_{−n} = △^{n}f(0) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}f(k) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}F_{k}.

Multiplying by (−1)^{n} and using the middle result gives

∑_{k=0}^{n} \binom{n}{k}(−1)^{k}F_{k} = −F_{n}.

Generalized Solution III by Don Redmond, Southern Illinois University, Carbondale, Illinois.

We generalize slightly. Let α and β be roots of the quadratic equation

x^{2} = ax + b,

where a and b are given numbers. Let

U_{n} = \frac{α^{n} − β^{n}}{α − β} and V_{n} = α^{n} + β^{n}.

Note that α + β = a and αβ = −b.

If 0 ≤ r ≤ n, then

∑_{k=0}^{n} \binom{n}{k}a^{n−k}(−1)^{k}U_{k+r} = ∑_{k=0}^{n} \binom{n}{k}a^{n−k}(−1)^{k} \frac{α^{k+r} − β^{k+r}}{α − β}

= \frac{1}{α − β} \{α^{r} ∑_{k=0}^{n} \binom{n}{k}a^{n−k}(−1)^{k}α^{k} − β^{r} ∑_{k=0}^{n} \binom{n}{k}a^{n−k}(−1)^{k}β^{k}\}

= \frac{1}{α − β} \{α^{r}(a − α)^{n} − β^{r}(a − β)^{n}\} = \frac{1}{α − β} \{α^{r}β^{n} − α^{n}β^{r}\}

= \frac{1}{α − β} (αβ)^{r}\{β^{n−r} − α^{n−r}\} = −(−b)^{r}U_{n−r}.

If a = b = 1, then U_{n} = F_{n}, and so we have, if r = 0,

∑_{k=0}^{n} \binom{n}{k}(−1)^{k}F_{k} = −F_{n}.

In a similar way, one can show that if 0 ≤ r ≤ n, then

∑_{k=0}^{n} \binom{n}{k}a^{n−k}(−1)^{k}V_{k+r} = (−b)^{r}V_{n−r}

and, in particular,

∑_{k=0}^{n} \binom{n}{k}(−1)^{k}L_{k} = L_{n}.

Comment by Gerald Bergum, South Dakota State University, Brookings, South Dakota.

The problem is a direct result of the identity

∑_{i=0}^{n} \binom{n}{i}(−1)^{i}F_{i+j} = (−1)^{j+1}F_{n−j},

which can be found on page 51 of the book Fibonacci and Lucas Numbers by Verner E. Hoggatt, Jr.

95. [1996, 90] Proposed by Stanley Rabinowitz, Westford, Massachusetts and Robert E. Kennedy and Curtis Cooper, Central Missouri State University, Warrensburg, Missouri.

Let n be a positive integer. It is known that

∑_{{k=1 \atop gcd(k,n)=1}}^{n} 1 = ϕ(n),

where ϕ is Euler’s phi function.

(a) Prove

∑_{{k=1 \atop gcd(k,n)=1}}^{n} k = \frac{1}{2}n · ϕ(n).

(b) Prove

∑_{{k=1 \atop gcd(k,n)=1}}^{n} k^{2} = \frac{1}{6}n(2n · ϕ(n) + ϕ^{−1}(n)),

where ϕ^{−1} is the Dirichlet inverse of Euler’s phi function.

(c)^{∗} Let m be a positive integer, m ≥ 3. Find a formula for

∑_{{k=1 \atop gcd(k,n)=1}}^{n} k^{m}.

Solution by Thomas C. Leong, The City College of City University of New York, New York, New York.

(a) Now (k, n) = 1 if and only if (n − k, n) = 1. Thus,

2 ∑_{{1≤k≤n \atop (k,n)=1}} k = ∑_{{1≤k≤n \atop (k,n)=1}} k + ∑_{{1≤k≤n \atop (k,n)=1}}(n − k) = ∑_{{1≤k≤n \atop (k,n)=1}} n = n · ϕ(n)

and the result follows.

(b) and (c) We show that

(1) ϕ_{m}(n) := ∑_{{1≤k≤n \atop (k,n)=1}} k^{m} = \frac{1}{m + 1} ∑_{j=0}^{m} \binom{m + 1}{j}B_{j}n^{m−j+1} ∏_{p|n}(1 − p^{j−1}),

where B_{j} denote the jth Bernoulli number (see, for example, Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer-Verlag, New York, 1990.) To prove this, we need several preliminary lemmas.

The first lemma is the well-known formula for summing the mth powers of the first n−1 natural numbers. We state it without proof. (For a proof, see Ireland and Rosen.)

\underline{Lemma 1}. Let S_{m}(n) = 1^{m} + 2^{m} + ⋯ + n^{m}. For n ≥ 1 and m ≥ 1

(2)  S_{m}(n − 1) = \frac{1}{m + 1} ∑_{j=0}^{m} \binom{m + 1}{j}B_{j}n^{m−j+1}.

The similarity between (1) and (2) is not a coincidence. Their connection is given in the next lemma.

\underline{Lemma 2}.

∑_{d|n} ϕ_{m}(d)(n/d)^{m} = S_{m}(n).

\underline{Proof}. Each fraction in the set H = \{h/n | 1 ≤ h ≤ n\} can be uniquely expressed in lowest terms: h/n = a/d where d|n, 1 ≤ a ≤ d, and (a, d) = 1. That is, each h, 1 ≤ h ≤ n, has a unique representation as

h = a\frac{n}{d} where d|n, 1 ≤ a ≤ d, and (a, d) = 1.

Conversely, each fraction a/d where d|n, 1 ≤ a ≤ d, and (a, d) = 1 is a member of H : a/d = h/n where 1 ≤ h ≤ n. That is, if d|n, 1 ≤ a ≤ d, and (a, d) = 1, then

a\frac{n}{d} = h where 1 ≤ h ≤ n.

Thus,

∑_{d|n} ϕ_{m}(d)(\frac{n}{d})^{m} = ∑_{d|n} ∑_{{1≤a≤d \atop (a,d)=1}} a^{m}(\frac{n}{d})^{m} = ∑_{d|n} ∑_{{1≤a≤d \atop (a,d)=1}}(a\frac{n}{d})^{m} = ∑_{h=1}^{n} h^{m} = S_{m}(n).

Let f_{m}(n) = n^{m}. The previous lemma, stated concisely, says ϕ_{m} ∗ f_{m} = S_{m}, where ∗ denotes Dirichlet convolution. Thus, if we know the Dirichlet inverse f_{m}^{−1} of f_{m}, we can find ϕ_{m}(n) by inverting:

ϕ_{m} = ϕ_{m} ∗ f_{m} ∗ f_{m}^{−1} = S_{m} ∗ f_{m}^{−1}.

Two more lemmas help us in this computation.

\underline{Lemma 3}. Let f_{m}(n) = n^{m} and μ(n) denote the Möbius function. Then,

f_{m}^{−1}(n) = μ(n)f_{m}(n).

\underline{Proof}. Indeed,

(f^{−1} ∗ f)(n) = ∑_{d|n} μ(d)f_{m}(d)f_{m}(\frac{n}{d}) = n^{m} ∑_{d|n} μ(d) = \{ \begin{matrix}1, & if n = 1; \\ 0, & if n > 1, \end{matrix}

where we have used the well-known formula

(3)  ∑_{d|n} μ(d) = \{ \begin{matrix}1, & if n = 1; \\ 0, & if n > 1. \end{matrix}

\underline{Lemma 4}. For any integer m,

∑_{d|n} d^{m}μ(d) = ∏_{p|n}(1 − p^{m}).

\underline{Proof}. Let g(n) = ∑_{d|n} d^{m}μ(d). Suppose (n_{1}, n_{2}) = 1. Then d|n_{1}n_{2} if and only

if d = d_{1}d_{2}, d_{1}|n_{1}, and d_{2}|n_{2}. Thus,

g(n_{1})g(n_{2}) = ( ∑_{d_{1}|n_{1}} d_{1}μ(d_{1}))( ∑_{d_{2}|n_{2}} d_{2}μ(d_{2}))

= ∑_{d_{1}|n_{1}} ∑_{d_{2}|n_{2}} d_{1}d_{2}μ(d_{1})μ(d_{2})

= ∑_{d_{1}|n_{1}} ∑_{d_{2}|n_{2}} d_{1}d_{2}μ(d_{1}d_{2})

= ∑_{d|n_{1}n_{2}} dμ(d)

= g(n_{1}n_{2}).

That is, g is multiplicative. Thus, to find g(n) we need only know the values g(p^{a}) for prime powers p^{a}. Since μ(p^{a}) = 0 for a > 1,

g(p^{a}) = ∑_{d|p^{a}} d^{m}μ(d) = 1^{m}μ(1) + p^{m}μ(p) = 1 − p^{m}

and consequently

g(n) = ∏_{p|n} g(p^{a}) = ∏_{p|n}(1 − p^{m}).

Finally, we invert. If n = 1, then ϕ_{m}(n) = 1. So suppose n > 1. Using our previous lemmas,

ϕ_{m}(n) = (S_{m} ∗ f_{m}^{−1})(n)

= ∑_{d|n} S_{m}(d)μ(\frac{n}{d})f_{m}(\frac{n}{d})

= ∑_{d|n} S_{m}(d)\frac{n^{m}}{d^{m}} μ(\frac{n}{d})

= ∑_{d|n} \{S_{m}(d − 1)\frac{n^{m}}{d^{m}} μ(\frac{n}{d}) + n^{m}μ(\frac{n}{d})\}

= ∑_{d|n} S_{m}(d − 1)\frac{n^{m}}{d^{m}} μ(\frac{n}{d}) + n^{m} ∑_{d|n} μ(\frac{n}{d})

= ∑_{d|n} S_{m}(d − 1)\frac{n^{m}}{d^{m}} μ(\frac{n}{d})

= ∑_{d|n} \frac{1}{m + 1} ∑_{j=0}^{m} \binom{m + 1}{j}B_{j}d^{m−j+1} \frac{n^{m}}{d^{m}} μ(\frac{n}{d})

= \frac{1}{m + 1} ∑_{j=0}^{m} ∑_{d|n} \binom{m + 1}{j}B_{j}n^{m} \frac{1}{d^{j−1}} μ(\frac{n}{d})

= \frac{1}{m + 1} ∑_{j=0}^{m} \binom{m + 1}{j}B_{j}n^{m−j+1} ∑_{d|n}(\frac{n}{d})^{j−1}μ(\frac{n}{d})

= \frac{1}{m + 1} ∑_{j=0}^{m} \binom{m + 1}{j}B_{j}n^{m−j+1} ∏_{p|n}(1 − p^{j−1}).

The first few Bernoulli numbers are B_{0} = 1, B_{1} = −\frac{1}{2}, B_{2} = \frac{1}{6}, B_{3} = 0, B_{4} = −\frac{1}{30}. Applying our formula in the case m = 1, 2, 3, 4 gives

∑_{{1≤k≤n \atop (k,n)=1}} k = \frac{1}{2}n^{2} ∏_{p|n}(1 − \frac{1}{p}) = \frac{1}{2}nϕ(n)

∑_{{1≤k≤n \atop (k,n)=1}} k^{2} = \frac{1}{3}n^{3} ∏_{p|n}(1 − \frac{1}{p}) + \frac{1}{6}n ∏_{p|n}(1 − p) = \frac{1}{3}n^{2}ϕ(n) + \frac{1}{6}n ∏_{p|n}(1 − p)

∑_{{1≤k≤n \atop (k,n)=1}} k^{3} = \frac{1}{4}n^{4} ∏_{p|n}(1 − \frac{1}{p}) + n^{2} ∏_{p|n}(1 − p) = \frac{1}{4}n^{3}ϕ(n) + n^{2} ∏_{p|n}(1 − p)

∑_{{1≤k≤n \atop (k,n)=1}} k^{4} = \frac{1}{5}n^{5} ∏_{p|n}(1 − \frac{1}{p}) + \frac{1}{3}n^{3} ∏_{p|n}(1 − p) − \frac{1}{30}n ∏_{p|n}(1 − p^{3})

= \frac{1}{5}n^{4}ϕ(n) + \frac{1}{3}n^{3} ∏_{p|n}(1 − p) − \frac{1}{30}n ∏_{p|n}(1 − p^{3}).

Note that inverting the well-known formula ∑_{d|n} ϕ(d) = n, we get ϕ = μ∗f_{1}. Thus,

ϕ^{−1} = μ^{−1} ∗ f_{1}^{−1}. Now from (3), we see that μ^{−1}(n) = 1 for all n. Applying lemmas 3 and 4, we have

ϕ^{−1}(n) = ∑_{d|n} f_{1}^{−1}(d) = ∑_{d|n} dμ(d) = ∏_{p|n}(1 − p).

Thus, the above formula for ϕ_{2}(n) and the one in the statement of the problem agree.

Also solved by Joseph B. Dence, University of Missouri-St. Louis, St. Louis, Missouri; Don Redmond, Southern Illinois University, Carbondale, Illinois; and James T. Bruening, Southeast Missouri State University, Cape Girardeau, Missouri. Parts (a) and (b) were also solved by the proposers.

96. [1996, 91] Proposed by Herta T. Freitag, Roanoke, Virginia.

Let an (m by 2) determinant

det ( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,3} & ⋯ & a_{1,m−1} & a_{1,m} \\ a_{2,1} & a_{2,2} & a_{2,3} & ⋯ & a_{2,m−1} & a_{2,m} \end{matrix} ) , m ≥ 3

be defined by S(m − 1) + \overline{D}, where

S(m − 1) = ∑_{r=1}^{m−1} det ( \begin{matrix}a_{1,r} & a_{1,r+1} \\ a_{2,r} & a_{2,r+1} \end{matrix} )

and

\overline{D} = det ( \begin{matrix}a_{1,m} & a_{1,1} \\ a_{2,m} & a_{2,1} \end{matrix} ) .

Consider an (m by 2) determinant D whose elements are polygonal numbers P_{n,k} (P_{5,3} is the 5th triangular number) and such that

a_{i,j} = P_{j,i+2},

where i = 1, 2 and j = 1, 2, 3, …, m. Evaluate D.

Solution by James T. Bruening, Southeast Missouri State University, Cape Girardeau, Missouri.

\underline{Solution}.

D = \frac{m(m − 1)(m − 2)}{6}.

\underline{Proof}.

\begin{matrix}det & ( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,3} & ⋯ & a_{1,m−1} & a_{1,m} \\ a_{2,1} & a_{2,2} & a_{2,3} & ⋯ & a_{2,m−1} & a_{2,m} \end{matrix} ) \\ = & det ( \begin{matrix}1 & 3 & 6 & ⋯ & \frac{m(m−1)}{2} & \frac{m(m+1)}{2} \\ 1 & 4 & 9 & ⋯ & (m − 1)^{2} & m^{2} \end{matrix} ) , \end{matrix}

so for all r, 1 ≤ r ≤ m − 1,

\begin{aligned}det ( \begin{matrix}a_{1,r} & a_{1,r+1} \\ a_{2,r} & a_{2,r+1} \end{matrix} ) & = det ( r^{2} (r + 1)^{2}^{\frac{r(r+1)}{2} \frac{(r+1)(r+2)}{2}} ) = \frac{r(r + 1)^{3}}{2} − \frac{r^{2}(r + 1)(r + 2)}{2} \\ & = \frac{r(r + 1)}{2}[r^{2} + 2r + 1 − r^{2} − 2r] = \frac{r(r + 1)}{2}. \end{aligned}

Then,

S(m − 1) = ∑_{r=1}^{m−1} det ( \begin{matrix}a_{1,r} & a_{1,r+1} \\ a_{2,r} & a_{2,r+1} \end{matrix} ) = ∑_{r=1}^{m−1} \frac{r(r + 1)}{2}

= \frac{1}{2} ∑_{r=1}^{m−1}(r^{2} + r) = \frac{1}{2}(\frac{m(m − 1)(2m − 1)}{6} + \frac{m(m − 1)}{2})

= \frac{1}{2} \frac{m(m − 1)}{2}(\frac{2m − 1 + 3}{3}) = \frac{m(m − 1)(m + 1)}{6}.

\begin{aligned}\overline{D} & = det ( \begin{matrix}a_{1,m} & a_{1,1} \\ a_{2,m} & a_{2,1} \end{matrix} ) = det ( \begin{matrix}\frac{m(m+1)}{2} & 1 \\ m^{2} & 1 \end{matrix} ) \\ & = \frac{m(m + 1)}{2} − m^{2} = −\frac{m(m − 1)}{2}. \end{aligned}

Thus,

S(m − 1) + \overline{D} = \frac{m(m − 1)(m + 1)}{6} − \frac{m(m − 1)}{2} = \frac{m(m − 1)}{2}(\frac{m − 2}{3}),

so that

D = \frac{m(m − 1)(m − 2)}{6}.

Also solved by the proposer.

/bye /bye