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

[anemone]

For $n=1,2,...,$ set $$S_n=\sum_{k=0}^{3n} {3n\choose k}$$ and $$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:

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

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

and determined the recursion:

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

The characteristic equation for this recursion is:

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

and so the closed form is:

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

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

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

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

Adding the two equations, we find:

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

Hence:

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

And so we find:

$$\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:

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

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

and determined the recursion:

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

The characteristic equation for this recursion is:

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

and so the closed form is:

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

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

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

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

Adding the two equations, we find:

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

Hence:

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

And so we find:

$$\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 $$S_n=\sum_{k=0}^{3n} {3n\choose k}$$ and $$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!:)