2015_II_3_Pure

nice combi result…
T_8-T_7 just gives the number of extra triangles producible by fixing the 8th rod as the largest (rather than any number < 8), which we can enumerate to show the result. we must ensure the triangle inequality holds for each triple. this gives the set of possibilities: \{[(1,7,8),(2,7,8),\ldots,(6,7,8)],[(2,6,8),\ldots,(5,6,8)],[(3,5,8),(4,5,8)]\} which is 6+4+2 as indicated by the []'s. T_8-T_6=T_8-T_7+T_7-T_6=2+4+6+T_7-T_6. we can repeat the process above to find T_7-T_6. the set produced this time is: \{[(1,6,7),\ldots,(5,6,7)],[(2,5,7),\ldots,(4,5,7)],[(3,4,7)]\} which gives 5+3+1 possibilities.
\therefore T_8-T_6=2+4+6+1+3+5.
it is apparent that

T_{2m}-T_{2m-1}=\sum_{k=1}^{m-1}2k=m(m-1), \\ T_{2m}-T_{2m-2}=\sum_{k=1}^{2m-2}k=(m-1)(2m-1).

for the base case in the induction, from 2m\geqslant 3 we find m=2. T_4 can just be enumerated by exhaustion, with the set being: \{(1,3,4),(2,3,4),(1,2,3)\} giving 3. from the formula, T_{2(2)}=\frac{1}{6}(2)(2-1)(4(2)+1)=18/6=3 so it holds in the base case.
now assume it holds for some m=k, k\in\mathbb{Z^+}.
from above we know

\begin{align} T_{2(k+1)}-T_{2k} &=\sum_{l=1}^{2k}l \\\implies T_{2(k+1)} &= \frac{1}{6}k(k-1)(4k+1) + \frac{1}{2}(2k)(2k+1) \\&= \frac{1}{2}k(\frac{1}{3}(k-1)(4k+1)+4k+2) \\&= \frac{k}{2}(4k^2/3-k+4k+2-1/3) \\&= \frac{k}{2}(\frac{1}{3}(4k^2+9k+5)) \\&= \frac {k}{6}(4k+5)(k+1) \\&= \frac{1}{6}(k+1)((k+1)-1)(4(k+1)+1) \end{align}

which completes the induction.

we can use

\begin{align} T_{2m}-T_{2m-1}&=m(m-1) \\\iff T_{2m-1}&=\frac{1}{6}m(m-1)(4m+1)-m(m-1) \\&=m(m-1)(1/6(4m+1)-1) \\&= \frac{1}{6}m(m-1)(4m-5) \end{align}
1 Like