Domino Sums Take 2

Let $k$ , for $0 \le k \le n$ , be one of the numbers in the domino set of order $n$ . Then the tiles containing $k$ are $(0, k), (1, k), \ldots (k, k), \ldots (n, k)$ . There are $n + 1$ such tiles, so due to the one double tile the number $k$ will appear on the tiles exactly $n + 2$ times. This gives us a formula for $T(n)$ :

$\begin{array}{rl} T(n) &= \ \ (n + 2) (1 + 2 + 3 + \ldots + n) \\ \\ &= \ \ (n + 2) \sum_{k = 0}^n k \\ \\ &= \ \ (n + 2) \left[ \dfrac{n(n + 1)}{2} \right] \\ \\ &= \dfrac{n(n + 1)(n + 2)}{2} \end{array}$

To generate a formula for $P(n)$ , we multiply $(0 + 1 + 2 + \ldots + n) (0 + 1 + 2 + \ldots + n) = (0 \cdot 0) + (0 \cdot 1) + (1 \cdot 0) + (0 \cdot 2) + (1 \cdot 1) + (2 \cdot 0) + \ldots + (n \cdot n)$ . This gives us all the terms we need, but every product not of the form $(k \cdot k)$ is represented twice.

To get around this, we add in a second set of $(k \cdot k)$ 's, so that now every term is included twice, and then take half of that sum.

$\begin{array}{rl} P(n) &= \ \ \dfrac{1}{2} \left[ (0 + 1 + 2 + \ldots + n) (0 + 1 + 2 + \ldots + n) + (1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 + \ldots +n \cdot n) \right] \\ \\ &= \ \ \dfrac{1}{2} \left[ \left( \sum_{k = 0}^n k \right)^2 + \sum_{k = 0}^n k^2 \right] \\ \\ &= \ \ \dfrac{1}{2} \left( \dfrac{n^2(n + 1)^2}{4} + \dfrac{n(n + 1)(2n + 1)}{6} \right) \\ \\ &= \ \ \dfrac{n(n + 1)}{24} \left[ 3n(n + 1) + 2(2n + 1) \right] \\ \\ &= \ \ \dfrac{n(n + 1)(n + 2)(3n + 1)}{24} \end{array}$

Then we have

$\begin{array}{rl} \dfrac{n \cdot T(n)}{P(n)} &= \ \ \dfrac{\dfrac{n^2(n + 1)(n + 2)}{2}}{\dfrac{n(n + 1)(n + 2)(3n + 1)}{24}} \\ \\ &= \ \ \dfrac{12n^2(n + 1)(n + 2)}{n(n + 1)(n + 2)(3n + 1)} \\ \\ &= \ \ \dfrac{12n}{3n + 1} \end{array}$

and so

$\begin{array}{rl} \lim_{n \to \infty} \dfrac{n \cdot T(n)}{P(n)} &= \ \ \lim_{n \to \infty} \dfrac{12n}{3n + 1} \\ \\ &= \boxed{4} \end{array}$

Note that

$\begin{aligned} T(n) & = \sum_{j=0}^n \sum_{k=j}^n (j+k) \\ & = \sum_{j=0}^n \left((n-j+1)j + \frac {n-j+1}2 (j+n) \right) \\ & = \sum_{j=0}^n \frac {(2n+3)j - 3j^2 + n(n+1)}2 \\ & = \frac 12 \left(\frac {n(n+1)(2n+3)}2 - 3 \times \frac {n(n+1)(2n+1)}6 + n(n+1)^2 \right) \\ & = \frac {n(n+1)(n+2)}2 \end{aligned}$

and that

$\begin{aligned} P(n) & = \sum_{\color{#3D99F6}j=0}^n \sum_{k=j}^n jk = \sum_{\color{#D61F06}j=1}^n \sum_{k=j}^n jk \\ & = \sum_{j=1}^n j \left(\frac {n-j+1}2 (j+n) \right) \\ & = \frac 12 \sum_{j=1}^n \left(n(n+1)j+j^2-j^3 \right) \\ & = \frac 12 \left(\frac {n^2(n+1)^2}2 + \frac {n(n+1)(2n+1)}6 - \frac {n^2(n+1)^2}4 \right) \\ & = \frac 12 \left(\frac {n^2(n+1)^2}4 + \frac {n(n+1)(2n+1)}6 \right) \\ & = \frac {n(n+1)(n+2)(3n+1)}{24} \end{aligned}$

Therefore,

$\begin{aligned} \lim_{n \to \infty} \frac {nT(n)}{P(n)} & = \lim_{n \to \infty} \frac {24n^2(n+1)(n+2)}{2n(n+1)(n+2)(3n+1)} \\ & = \lim_{n \to \infty} \frac {12n}{3n+1} & \small \color{#3D99F6} \text{Divide up and down by }n \\ & = \lim_{n \to \infty} \frac {12}{3+\frac 1n} \\ & = \boxed{4} \end{aligned}$

By arranging the dominoes, we can write $T(n)$ as : $\sum_{i=0}^{n} (\sum_{j=i}^{n} i+j)$ and $P(n)$ as $\sum_{i=0}^{n} (\sum_{j=0}^{i} i\cdot j)$

Hence $T(n) = \sum_{i=0}^{n} (n+i-1)*i+(\sum_{j=i}^{n} j) = \sum_{i=0}^{n} ((n+i-1)*i + \frac{n(n+1)}{2}-\frac{i(i-1}{2}) = \frac{n(n+1)}{2} + \sum_{i=0}^{n} (n-\frac{3}{2})*i^2+\frac{i}{2} = \frac{n(n^2+3n+2)}{2} = \frac{n(n+1)(n+2)}{2}$

Similarly, $P(n) = \sum_{i=0}^{n} i\cdot(\sum_{j=i}^{n} j) = \sum_{i=0}^{n} \frac{i^2(i+1)}{2} = \frac{1}{2}\sum_{i=0}^{n} i^3 + i^2 = \frac{n(n+1)(2n+1)}{6} + \frac{(n(n+1))^2}{4} = \frac{n(n+1)(n+2)(3n+1)}{24}$

Thus :

$\lim_{n->\infty} \frac{nT(n)}{P(n)}= \lim_{n->\infty} \frac{12n^2(n^2+3n+2)}{n(n+1)(n+2)(3n+1)} = \lim_{n->\infty} \frac{12n^4}{3n^4} = \frac{12}{3} = \boxed{4}$

Since we only want to compute $\lim\limits_{n \to \infty} \frac{n T(n)}{P(n)}$ it is not necessary to calculate $T(n)$ and $P(n)$ in full detail. We will estimates them (sufficiently).

Preamble: (what you need to know)

We will make use of the telescope-identity $a_n-a_0 =\sum\limits^n_{k=1}\left( a_{k}-a_{k-1}\right)$ which can simply proven by canceling the middle terms (See A1).

and we will use the following "antiderivitive"-rule, which is a discrete equivalent to $\displaystyle \int t^l \,\mathrm{d} t=\tfrac1{l+1}t^{l+1}$ :

Let $n$ be a non-negative integer, then $F(n)=\sum\limits^n_{k=1} k^l$ is a polynomial of degree $l+1$ with leading coefficient $\frac1{l+1}$ . (See A2.)

Furthermore if $f(k)$ is a polynomial of degree $l$ with leading coefficient $a_l$ , then $F(n)=\sum\limits^n_{k=1} f(k)$ is a polynomial of degree $l+1$ leaded by the coefficient $\dfrac{a_l}{l+1}$ .

The Solution:

By the telescope-identity we get $\quad T(n) = T(0)+\sum\limits^{n}_{k=1}(T(k)-T(k-1))\quad$ and the same for $P$ instead of $T$ . But $T(k)-T(k-1)$ is just sum for the domino pairs containing $k$ which are the $k+1$ dominos $(k, j)$ for $0 \leq j \leq k$ .

So the sum is $\quad \sum^k_{j=0} (k+j)=(k+1)k+\sum^k_{j=0}j\quad$ and using "antiderivitive"-rule we get $T(k)-T(k-1) = (k+1)k+\sum^k_{j=0}j = k^2+k+(\tfrac12 k^2+r_1(k)) =\tfrac32k^2 +\tilde r_1(k)$
with $\tilde r_1(k)$ a degree 1 or less polynomial. And hence $T(n) = T(0)+\sum\limits^{n}_{k=1}(T(k)-T(k-1))= T(0)+\sum\limits^{n}_{k=1}\left(\tfrac32k^2 +\tilde r_1(k)\right) = T(0)+\tfrac13\cdot \tfrac32 n^3+\sum\limits^{n}_{k=1}\tilde r_1(k) = \tfrac12 n^3+ r_T(n)$ where $r_T(n)$ is a polynomial with degree 2 or less.

For $P(k)-P(k-1)$ is the sum of the product of the domino pairs $(k,j)$ and thus: $P(k)-P(k-1)= \sum^{k}_{j=0}k \cdot j =k\cdot \sum^{k}_{j=0}j=k \cdot (\tfrac12 k^2+r_1(k)) = \tfrac12 k^3+r_2(k)$ with $r_2(k)$ a polynomial of degree 2 or less.

Using the same Idea for $P$ we estimate $P(n) = P(0)+\sum\limits^{n}_{k=1}(P(k)-P(k-1))= P(0)+\sum\limits^{n}_{k=1} \left(\tfrac12 k^3+r_2(k)\right)=P(0)+\tfrac14 \cdot \tfrac12 n^4 +\sum\limits^{n}_{k=1}r_2(k) = \tfrac18 n^4+r_P(n)$ with $r_P(n)$ a polynomial of degree 3 or less.

Since $r_T(n)$ and $r_P(n)$ are polynomials of degree 2 and 3 respectively, $\dfrac{r_T(n)}{n^3}$ and $\dfrac{r_P(n)}{n^4}$ tend to be $0$ for $n \to \infty$ .

Now we calculate $\lim\limits_{n \to \infty} \frac{n T(n)}{P(n)} = \lim\limits_{n \to \infty} \frac{n \left(\tfrac12 n^3+ r_T(n)\right)}{\tfrac18 n^4+r_P(n)} = \lim\limits_{n \to \infty} \frac{n^4 \left(\tfrac12+ \tfrac{r_T(n)}{n^3}\right)}{n^4\left(\tfrac18+\tfrac{r_P(n)}{n^4}\right)} = \underline{\underline{4}}$

Appendix

A1: $\sum\limits^n_{k=1}\left( a_{k}-a_{k-1}\right)=\left(\sum\limits^n_{k=1}a_{k}\right)-\left(\sum\limits^n_{k=1}a_{k-1}\right)=\sum\limits^n_{k=1}a_{k}-\sum\limits^{n-1}_{k=0}a_{k}= a_n + \left(\sum\limits^{n-1}_{k=1}a_{k}\right)-\left(\sum\limits^{n-1}_{k=1}a_{k}\right)-a_0=a_n-a_0$

A2: Using the binomial theorem $(a+b)^l=\sum\limits^l_{i=0} \binom{n}{i}a^{l-i}b^{i}$ we will get the identity $k^{l+1} - (k-1)^{l+1} = k^{l+1} - \sum\limits^{l+1}_{i=0} \binom{l+1}{i}k^{l+1-i}(-1)^{i} = \sum\limits^{l+1}_{\color{#D61F06}i=1} \binom{l+1}{i}k^{l+1-i}(-1)^{\color{#D61F06}i+1}$ and with above telescope-identity $n^{l+1}=n^{l+1}-0^{l+1} = \sum^n_{k=1} k^{l+1} - (k-1)^{l+1} = \sum^n_{k=1}\sum\limits^{l+1}_{i=1} \binom{l+1}{i}k^{l+1-i}(-1)^{i+1}= \sum^n_{k=1} \left((l +1)k^{l}+ r(k)\right)$ So every Monomial $n^{l+1}$ is just a sum of a polynomial $p(k)$ of degree $l$ with leading coefficient $l+1$ . The $r(k)$ is the rest-term which is of degree $l-1$ .

As polynomials of degree $j$ the $p_j(k) :=\sum\limits^{j+1}_{i=1} \binom{j+1}{i}k^{j+1-i}(-1)^{i+1}$ for different $j$ are indepentent and $k^l$ is just a combination of the ones with degree $j \leq l$ . The leading coefficient for $p_l(k)$ have to be $\frac1{l+1}$ (why?). Hence $\sum\limits^n_{k=1} k^l = P(n)$ is the same combination of the $\sum\limits^n_{k=1}p_j(k)$ and therefore a Polynomial of degree $l+1$ with leading coefficient $\frac1{l+1}$ .

Integer Sequence Database and Wolfram are needed for this to work.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import scipy.special
import itertools
final, final1 = [], []
def totals(n):
    thelist = list(itertools.combinations(list(range(n+1)), 2))
    counter = 0
    for z in thelist:
        counter += z[0]
        counter += z[1]
    counter += n*(n+1)
    return counter
def product(n):
    thelist = list(itertools.combinations(list(range(n+1)), 2))
    counter = 0
    temp = 0
    for z in thelist:
        temp = z[0]*z[1]
        counter += temp
    counter += n*(n+1)*(2*n+1)/6
    return int(counter)
for x in range(15):
    final.append(totals(x))
for x in range(15):
    final1.append(product(x))
print(final)
print(final1)