4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ One suggestion is first proving that the sequence exhibits symmetry. Then it seems that Galois theory will work. $\endgroup$ – i707107 Jul 16 '16 at 18:09
  • $\begingroup$ @i707107 How would we use Galois theory? Also, we may be able to show that $a(2-\sqrt{3})^x+b(2+\sqrt{3})^y = b(2-\sqrt{3})^x+a(2+\sqrt{3})^y$ where $x,y$ are integers if and only if $a(2-\sqrt{3})^x+b(2+\sqrt{3})^y$ is an integer. $\endgroup$ – user19405892 Jul 16 '16 at 18:26
  • $\begingroup$ I am thinking about it. If we are able to prove that the sequence is symmetric, then by Galois theory, each term will be fixed by the nontrivial automorphism $\sigma : \sqrt 3 \rightarrow -\sqrt 3$. $\endgroup$ – i707107 Jul 16 '16 at 18:28
  • $\begingroup$ So far, I found that $t_{n+1,1}=4t_{n,1}-t_{n-1,1}$ and $t_{n+1,2}=14t_{n,2}-t_{n-1,2} + 1$. $\endgroup$ – i707107 Jul 16 '16 at 19:36
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ So does this work for any quadratic integer instead of $2+\sqrt3$? Then maybe it's more readable if you write $\alpha=2+\sqrt3$, $\overline\alpha=2-\sqrt3$. $\endgroup$ – rabota Jul 16 '16 at 20:49
  • $\begingroup$ Thank you. Edited as you commented. I think it will work for any quadratic integer instead of $2\pm\sqrt 3$. $\endgroup$ – i707107 Jul 16 '16 at 21:00
  • $\begingroup$ I think that after "From the recurrence relation, we have" you use that $\alpha\overline\alpha=1$. $\endgroup$ – rabota Jul 16 '16 at 21:06
  • $\begingroup$ That's true. For general case of quadratic integers, I would put $(\alpha \overline{\alpha})$ instead. $\endgroup$ – i707107 Jul 16 '16 at 21:07
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.