Prove that all $t_{n,m}$ are integers

Question

A "number triangle" $(t_{n, k})$ $(0 \le k \le n)$ is defined by $t_{n,0} = t_{n,n} = 1$ $(n \ge 0),$ $$t_{n+1,m} =(2 -\sqrt{3})^mt_{n,m} +(2 +\sqrt{3})^{n-m+1}t_{n,m-1} \quad (1 \le m \le n).$$ Prove that all $t_{n,m}$ are integers.

I find it hard to prove that they are all integers because from the table below there doesn't seem to be a pattern. I think induction might work if we use strong induction on $m$ for a fixed $n$. We know that it holds for $t_{n,0}$ so we have the base case. How should I write the inductive proof?

Assume that $t_{n,k}$ are integers for all $n < r$. Now, we have $$t_{r,1} = (2-\sqrt{3})t_{r-1,1}+(2+\sqrt{3})^{r-1}t_{r-1,0} = (2-\sqrt{3})t_{r-1,1}+(2+\sqrt{3})^{r-1}.$$ Then we have $t_{r-1,1} = (2-\sqrt{3})t_{r-2,1}+(2+\sqrt{3})^{r-2}t_{r-2,0} = (2-\sqrt{3})t_{r-2}+(2+\sqrt{3})^{r-2}$, which we know is an integer, but I don't see where to go from here.

Here is a table I made:

$t_{0,0} = 1$

$t_{1,0} = 1$

$t_{1,1} = 1$

$t_{2,0} = 1$

$t_{2,1} = (2-\sqrt{3})+(2+\sqrt{3}) = 4$

$t_{2,2} = 1$

$t_{3,0} = 1$

$t_{3,1} = (2-\sqrt{3})t_{2,1}+(2+\sqrt{3})^2 t_{2,0} = 4(2-\sqrt{3})+(2+\sqrt{3})^2 = 15$

$t_{3,2} = (2-\sqrt{3})^2 t_{2,2}+(2+\sqrt{3}) t_{2,1} = (2-\sqrt{3})^2+4(2+\sqrt{3}) = 15$

$t_{3,3} = 1$

$t_{4,0} = 1$

$t_{4,1} = (2-\sqrt{3}) t_{3,1}+(2+\sqrt{3})^3 t_{3,0} = 15(2-\sqrt{3})+(2+\sqrt{3})^3 = 56$

$t_{4,2} = (2-\sqrt{3})^2 t_{3,2}+(2+\sqrt{3})^2t_{3,1}= 15(2-\sqrt{3})^2 +15(2+\sqrt{3})^2 = 210$

$t_{4,3}= (2-\sqrt{3})^3 t_{3,3}+(2+\sqrt{3})t_{3,2} = (2-\sqrt{3})^3+15(2+\sqrt{3}) = 56$

$t_{4,4} = 1$

$t_{5,0} = 1$

$t_{5,1} = (2-\sqrt{3})t_{4,1}+(2+\sqrt{3})^4 t_{4,0} = 56(2-\sqrt{3})+(2+\sqrt{3})^4 = 209$

$t_{5,2} = (2-\sqrt{3})^2 t_{4,2}+(2+\sqrt{3})^4 t_{4,1} = 210(2-\sqrt{3})^2+56(2+\sqrt{3})^3 = 2926$

$t_{5,3} = (2-\sqrt{3})^3 t_{4,3}+(2+\sqrt{3})^2 t_{4,2} = 56(2-\sqrt{3})^3+210(2+\sqrt{3})^2 = 2926$

$t_{5,4} = (2-\sqrt{3})^4 t_{4,4}+(2+\sqrt{3}) t_{4,3} = (2-\sqrt{3})^4+56(2+\sqrt{3})^2 = 209$

$t_{5,5} = 1$

$t_{6,0} = 1$

$t_{6,1} = (2-\sqrt{3})t_{5,1}+(2+\sqrt{3})^{5}t_{5,0} = 209(2-\sqrt{3})+(2+\sqrt{3})^5 = 780$

$t_{6,2} = (2-\sqrt{3})^2 t_{5,2}+(2+\sqrt{3})^4 t_{5,1} = 2926(2-\sqrt{3})^2+209(2+\sqrt{3})^4 = 40755$

$t_{6,3} = (2-\sqrt{3})^3 t_{5,3}+(2+\sqrt{3})^3 t_{5,2} = 2926(2-\sqrt{3})^3+2926(2+\sqrt{3})^3 = 152152$

$t_{6,4} = (2-\sqrt{3})^4 t_{5,4}+(2+\sqrt{3})^{2}t_{5,3} = 209(2-\sqrt{3})^4+2926(2+\sqrt{3})^3 = 40755$

$t_{6,5} = (2-\sqrt{3})^5 t_{5,5}+(2+\sqrt{3})t_{5,4} = (2-\sqrt{3})^5+209(2+\sqrt{3}) = 780$

$t_{6,6} = 1$

Answer 1

Let$\require{begingroup}\begingroup\newcommand\oalpha{\overline\alpha}$ $\alpha=2+\sqrt3$, $\oalpha=2-\sqrt3$.

Let $P_n(x)=t_{n,0}+t_{n,1}x+\cdots+t_{n,n}x^n$.

By the recurrence relation, $$\begin{align*}P_{n+1}(x)&=\sum_{m=0}^n\oalpha^mt_{n,m}x^m+\sum_{m=1}^{n+1}\alpha^{n-m+1}t_{n,m-1}x^m\\&=P_n(\oalpha x)+P_n(x/\alpha)\alpha^nx\\&=P_n(\oalpha x)(1+\alpha^nx)\end{align*}$$ because $\alpha\oalpha=1$. It is now clear by induction that $$P_n(x)=\prod_{m=0}^{n-1}(1+\alpha^m\oalpha^{n-m-1}x),$$ so by symmetry, $$\overline{P_n(x)}=P_n(x)$$ (where $\overline{\;\vphantom 5\;}$ denotes conjugation in $\mathbb Z[\sqrt3][x]$) which means $P_n(x)\in\mathbb Z[x]$.

Note: This works for any algebraic $\alpha$ of degree $\leq2$ with $\alpha\oalpha=1$. For $\alpha=1$, we get Pascal's triangle and $P_n(x)=(1+x)^n$, in accordance with the binomial expansion.$\endgroup$

Answer 2

The base case is $t_{n,0}=t_{n,n}=1$ for all $n$. By assigning $0$ for $t_{n,m}$ with $m<0$ or $m>n$ or $n<0$, we see that the recurrence holds for all $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$.

Let $n\geq 0$ and $0\leq m \leq n$. Our induction hypothesis is

$$ t_{n',m} \in \mathbb{Z} \ \ \textrm{for all} \ \ 0\leq m\leq n'\leq n. $$

From this, we will prove that $t_{n+1,m}$ is an integer. Then we are done.

Let $\alpha = 2+\sqrt 3$ and $\overline{\alpha}=2-\sqrt3$. From the recurrence relation, we have by $\alpha \overline{\alpha} = 1$, $$ t_{n+1,m} - \alpha^m t_{n,m}= \overline{\alpha}^m t_{n,m} - t_{n-1, m} + \alpha^{n-m+1} t_{n,m-1} - \alpha^n t_{n-1, m-1}. $$

Then $$ t_{n+1,m}= ( \alpha^m + \overline{\alpha}^m)t_{n,m} -t_{n-1,m} + \alpha^{n-m+1}t_{n,m-1} - \alpha^n t_{n-1,m-1}.$$

Since $\alpha^m + \overline{\alpha}^m\in \mathbb{Z}$ for all $m\geq 0$, it is enough to show that $$\alpha^{n-m+1}t_{n,m-1} - \alpha^n t_{n-1,m-1}\in\mathbb{Z}.$$

Writing the recurrence for $t_{n,m-1}$, we have $$ t_{n,m-1} = \overline{\alpha}^{m-1} t_{n-1,m-1} + \alpha^{n-m+1} t_{n-1,m-2}. $$

By the induction hypothesis, $t_{n,m-1}\in\mathbb{Z}$, $t_{n-1,m-1}\in\mathbb{Z}$, $t_{n-1,m-2}\in\mathbb{Z}$. By applying the nontrivial automorphism $\sigma$ of $\mathbb{Q}(\sqrt 3)$ (which fixes $\mathbb{Q}$ and maps $\sqrt 3$ to $-\sqrt 3$), it follows that $$ t_{n,m-1} = \alpha^{m-1} t_{n-1,m-1} + \overline{\alpha}^{n-m+1} t_{n-1,m-2}. $$

Thus, we have $$ \alpha^{n-m+1}t_{n,m-1} - \alpha^n t_{n-1,m-1}=t_{n-1,m-2}\in\mathbb{Z}. $$ This proves the claim and we are done.

As a byproduct, we obtained a new recurrence $$ t_{n+1,m}= ( \alpha^m+\overline{\alpha}^m) t_{n,m} -t_{n-1,m} + t_{n-1,m-2}. $$

Answer 3

I think that we can find an explicit formula for $t_{n,m}$. To see how the formula is found, suppose for the moment that we know that $t_{n,m}$ is in $\mathbb{Z}$ for all $n,m$ with $n\geq m$. Then as we have the formula

$$t_{n+1,m} =(2 -\sqrt{3})^mt_{n,m} +(2 +\sqrt{3})^{n-m+1}t_{n,m-1} $$ we must have also $$t_{n+1,m} =(2 +\sqrt{3})^mt_{n,m} +(2 -\sqrt{3})^{n-m+1}t_{n,m-1}$$ Put $\displaystyle v_k=\frac{(2+\sqrt{3})^k-(2-\sqrt{3})^k}{2\sqrt{3}}$. Then if we substract the two formula, we get $\displaystyle t_{n,m}=\frac{v_{n-m+1}}{v_m}t_{n,m-1}$. Now it is easy to see that $t_{n,1}=\frac{v_n}{v_1}$ (note that $v_1=1$). Hence we get that we must have $$t_{n,m}=\frac{v_{n-m+1}\cdots v_n}{v_1\cdots v_m}$$

Of course, we have not proven anything, but now as the formula is clearly true if $n=m$, it is easy to show that it is true for $n\geq m$ by induction : Suppose that it is true for $t_{n,m-1}$, you show that this is true for $t_{n,m}$ by induction on $n\geq m$.

Once you have proven the formula, you get (as it is clear that $v_k\in \mathbb{Z}$ for all $k\geq 1$) that $t_{n,m}$ is rational. But from the recurrence formula, we get that $t_{n,m}$ is in $\mathbb{Z}[\sqrt{3}]$, hence an algebraic integer; so $t_{n,m}$ is in $\mathbb{Z}$ for all $n\geq m$.