I am trying to find solution of this recurrence $T(n+1,k+1) = T(n,k) + k \times \left( T(n,k+1) \right)$
Is T(n+1,k+1) = S(n,k) ? Based on this interpretation I have verified for many values given a tree. It is still very difficult for me to prove. S(n,k) is Stirling number of second kind.
Based on my recollection, @Gautam gave a very interesting interpretation for this a long time ago. He suggests that T(n+1,k+1) is the number of k independent vertices set for n vertices tree. https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
I think I could justify this in a similar way to Stirling number of second kind proof. But here, we get $k \times T(n,k+1)$ because while adding a leaf you could add the newly added vertex in k number of ways to form independent sets.
Stirling numbers of the second kind $S(n,k)$ satisfy the same recurrence relation as $T(n+1,k+1)$, so the $T(n+1,k+1)=S(n,k)$ provided you have the coincidence at initial conditions.
The number of $k>2$ independent vertices set for $n$-vertex tree depends on a tree. For instance, if a tree is a path and $k>\lceil n/2\rceil$, there is no such sets. From the other hand, for $n>k\ge 2$ a star with $n-1$ leaves has ${n-1 \choose k}$ such sets. For $n\ge k=2$ such sets are all (unordered) pairs of distinct vetices of the tree (which number is ${n \choose 2}$), but pairs of adjacent verices (which number is exactly the number of edges of the tree, that is $n-1$). So in this case the number of such sets eqauls $${n \choose 2}-(n-1)={n \choose 2}-{n-1 \choose 1}={n-1 \choose 2}.$$