@AKASH G and @Sunnidhya Roy
This is your closed form expression for the given problem:
1. For $n \geq 6 $ and $n=even$
$$T(n) = 2^{n-1} + \Sigma_{i=n-3}^{i=i-2 \ \& \ i\geq 3} \ \left(\frac{n(n-1)...(i+2)}{(n-i-1)!}\right)2^{i} + 2 \Sigma_{i=1}^{n-1} \ i$$
2. For $n \geq 7 $ and $n=odd$
$$T(n) = n \times 2^{n-2} + \Sigma_{i=n-4}^{i=i-2 \ \& \ i\geq 3} \ \left(\frac{n(n-1)...(i+2)}{(n-i-1)!}\right)2^{i} + 2 \Sigma_{i=1}^{n-1} \ i$$
This is from my observation for the given problem and I can provide proof for it if you want. You can further simplify it if you want. Since, the given recurrence is promising but it is not proved, So, I have not taken it.
@gatecse if you observe in the @Sunnidhya Roy’s image, “+2” comes when $n$ is even. because for even $n$ you have to append some pairs, for example, when $n=6,$ $(1,5),(5,1),(3,3)$ are added and same for other even values of $n.$ But when $n$ is odd then you don’t have to add pairs, you just have to append $2s.$
Now, when $n$ is even, the value of the newly added pairs are: $\binom {n}{1}+ \binom {n}{3}+ \binom {n}{n-1} = 2^{n-1} = 2^{n-1}\ – \ 2 + 2 =2(2^{n-2}-1) + 2 .$ Now, for even $n,$ $2^{n-2}-1$ is multiple of $3.$ You can prove it as: for even $n,$ and $n \geq 4$, $(n-2)$ is even and so, you can write it as $2^{2k} \ – \ 1 = 4^k – 1 = (1+3)^k – 1$ and now, use binomial expansion and you will get terms which are multiple of 3. Now, for other terms for $T(n)$ contains $3!,$ So, they are also multiple of 3 and so, you get terms multiple of 3 and added “+2” for even values of $n.$
