Can you prove the combinatorics challenge and find the value of |S_n-3T_n|?

[anemone]

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]

My solution:

Spoiler

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]

My solution:

Spoiler

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]

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]

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!:)