How can I prove $\frac{1}{n}\sum\limits_{d|n}\varphi(d)2^{n/d}=2+\sum\limits_{k=1}^{n-1}T(n-k,k)$?

Here $$T(n,k)=\sum\limits_{d|\gcd(n,k)}\frac{\varphi(d)}{n+k}\binom{(n+k)/d}{n/d}$$

First I need to show where from this formulas came up.

2) 00, 01=10, 11

3) 000, 001=010=100, 011=110=101, 111

4) 0000, 0001=0010=0100=1000, 0011=0110=1100=1001, 0101=1010, 0111=1110=1101=1011, 1111

etc., so we have:

2) {00, 10, 11}

3) {000, 100, 110, 111}

4) {0000, 1000, 1100, 1010, 1110, 1111}

5) {00000, 10000, 11000, 10100, 11100, 11010, 11110, 11111}

6) {000000, 100000, 110000, 101000, 100100, 111000, 110100, 110010, 101010, 111100, 111010, 110110, 111110, 111111}

or, more concretely:

2) {00}{01}{11}

3) {000}{100}{110}{111}

4) {0000}{1000}{1100, 1010}{1110}{1111}

5) {00000}{10000}{11000, 10100}{11100, 11010}{11110}{11111}

6) {000000}{100000}{110000, 101000, 100100}{111000, 110100, 110010, 101010}{111100, 111010, 110110}{111110}{111111}

then we can say, that

2) 1+1+1=3

3) 1+1+1+1=4

4) 1+1+2+1+1=6

5) 1+1+2+2+1+1=8

6) 1+1+3+4+3+1+1=14

7) 1+1+3+5+5+3+1+1=20

If we go to OEIS and write this, we can find two sequence (A000031, A241926).

Why are they have those formulas? Why if we make diagonal summation in second and add to result $2$ it will be equal to one of the terms of first?

If I made some mistakes, sorry for my English.

$$2+\frac{1}{n} \sum_{k=1}^{n-1} \sum_{d|\gcd(n,k)} \varphi(d) {n/d\choose (n-k)/d} \\ = 2+\frac{1}{n} \sum_{k=1}^{n-1} \sum_{d|\gcd(n,k)} \varphi(d) {n/d\choose k/d}.$$
$$2 + \frac{1}{n} \sum_{d|n} \sum_{k=1, \; d|\gcd(n,k)}^{n-1} \varphi(d) {n/d\choose k/d} \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{q=1}^{\lfloor (n-1)/d \rfloor} {n/d\choose q} \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) \left( - {n/d\choose 0} - {n/d\choose n/d} + 2^{n/d} \right) \\ = 2 + \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d} - 2 \frac{1}{n} \sum_{d|n} \varphi(d) \\ = \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}.$$