# Combinatorics Challenge

#### anemone

##### MHB POTW Director
Staff member
For $n=1,2,...,$ set $$\displaystyle S_n=\sum_{k=0}^{3n} {3n\choose k}$$ and $$\displaystyle T_n=\sum_{k=0}^{n} {3n\choose 3k}$$.

Prove that $|S_n-3T_n|=2$.

#### MarkFL

Staff member
My solution:

For the first sum, we may simply apply the binomial theorem to obtain the closed form:

$$\displaystyle S_n=\sum_{k=0}^{3n}{3n \choose k}=(1+1)^{3n}=8^n$$

For the second sum, I looked at the first 5 values:

$$\displaystyle T_1=2,\,T_2=22,\,T_3=170,\,T_4=1366,\,T_5=10922$$

and determined the recursion:

$$\displaystyle T_{n+1}=7T_{n}+8T_{n-1}$$

The characteristic equation for this recursion is:

$$\displaystyle r^2-7r-8=(r+1)(r-8)=0$$

and so the closed form is:

$$\displaystyle T_{n}=k_1(-1)^n+k_28^n$$

Using the initial values to determine the parameters, we may write:

$$\displaystyle T_{1}=-k_1+8k_2=2$$

$$\displaystyle T_{2}=k_1+64k_2=22$$

Adding the two equations, we find:

$$\displaystyle 72k_2=24\implies k_2=\frac{1}{3}\implies k_1=\frac{2}{3}$$

Hence:

$$\displaystyle T_{n}=\frac{1}{3}\left(2(-1)^n+8^n \right)$$

And so we find:

$$\displaystyle \left|S_n-3T_n \right|=\left|8^n-3\left(\frac{1}{3}\left(2(-1)^n+8^n \right) \right) \right|=\left|8^n-2(-1)^n-8^n \right|=\left|2(-1)^{n+1} \right|=2$$

Shown as desired.

#### anemone

##### MHB POTW Director
Staff member
My solution:

For the first sum, we may simply apply the binomial theorem to obtain the closed form:

$$\displaystyle S_n=\sum_{k=0}^{3n}{3n \choose k}=(1+1)^{3n}=8^n$$

For the second sum, I looked at the first 5 values:

$$\displaystyle T_1=2,\,T_2=22,\,T_3=170,\,T_4=1366,\,T_5=10922$$

and determined the recursion:

$$\displaystyle T_{n+1}=7T_{n}+8T_{n-1}$$

The characteristic equation for this recursion is:

$$\displaystyle r^2-7r-8=(r+1)(r-8)=0$$

and so the closed form is:

$$\displaystyle T_{n}=k_1(-1)^n+k_28^n$$

Using the initial values to determine the parameters, we may write:

$$\displaystyle T_{1}=-k_1+8k_2=2$$

$$\displaystyle T_{2}=k_1+64k_2=22$$

Adding the two equations, we find:

$$\displaystyle 72k_2=24\implies k_2=\frac{1}{3}\implies k_1=\frac{2}{3}$$

Hence:

$$\displaystyle T_{n}=\frac{1}{3}\left(2(-1)^n+8^n \right)$$

And so we find:

$$\displaystyle \left|S_n-3T_n \right|=\left|8^n-3\left(\frac{1}{3}\left(2(-1)^n+8^n \right) \right) \right|=\left|8^n-2(-1)^n-8^n \right|=\left|2(-1)^{n+1} \right|=2$$

Shown as desired.
Hey thanks for participating MarkFL! And I'm so impressed that you were so fast in cracking this problem!

#### caffeinemachine

##### Well-known member
MHB Math Scholar
For $n=1,2,...,$ set $$\displaystyle S_n=\sum_{k=0}^{3n} {3n\choose k}$$ and $$\displaystyle T_n=\sum_{k=0}^{n} {3n\choose 3k}$$.

Prove that $|S_n-3T_n|=2$.
Define $f(x)=\sum_{k=0}^{3n}{3n\choose k}x^k$.

Then $f(1)+f(\omega)+f(\omega^2)=3T_n$, where $\omega$ is a complex cube root of unity. Note that $f(1)=S_n$. So we get $S_n-3T_n=-[(1+\omega)^{3n}+(1+\omega^2)^{3n}]=-2$

#### anemone

##### MHB POTW Director
Staff member
Define $f(x)=\sum_{k=0}^{3n}{3n\choose k}x^k$.

Then $f(1)+f(\omega)+f(\omega^2)=3T_n$, where $\omega$ is a complex cube root of unity. Note that $f(1)=S_n$. So we get $S_n-3T_n=-[(1+\omega)^{3n}+(1+\omega^2)^{3n}]=-2$
Hi caffeinemachine,

Thanks for participating and I really appreciate you adding another good solution to this problem and my thought to solve this problem revolved around the idea that you used too!