Is there a general formula to prove the equivalency of these two expansions of $~\dfrac{1}{(1-x)^2}~$? So we know the expansion of $$\dfrac{1}{(1-x)^2}=1+2x+3x^2+4x^3+\cdots~,$$ we can get this expression by $$\frac{1}{(1-x)^2}=\frac{1}{1-x}\frac{1}{1-x}=(1+x+x^2+x^3+\cdots)^2=1+2x+3x^2+4x^3+\cdots$$
Now if we square the denominator first: $$\frac{1}{(1-x)^2}=\frac{1}{1-(2x-x^2)}~,$$ then expand and get: $$\dfrac{1}{(1-x)^2}=1+(2x-x^2)+(2x-x^2)^2+(2x-x^2)^3+\cdots~.$$ This looks a bit messy but if I expand the brackets and sort the terms by the powers of $~x~$ (keeping the binomial coefficients) we would get: 
\begin{align}
1+2x&+\bigg[2^2-{1\choose1}\bigg]x^2\\&+ \bigg[2^3-{2\choose1}\times2\bigg]x^3\\& + \bigg[2^4-{3\choose1}\times2^2+{2\choose2}\bigg]x^4 \\&+ \bigg[2^5-{4\choose1}\times2^3+{3\choose2}\times2\bigg]x^5 \\&+ \bigg[2^6-{5\choose1}\times2^4+{4\choose2}\times2^2-{3\choose3}\bigg]x^6 \\&+ \bigg[2^7-{6\choose1}\times2^5+{5\choose2}\times2^3-{4\choose3}\times2\bigg]x^7+... 
\end{align} equate this expression to $1+2x+3x^2+4x^3+...$ we would get: $$n+1=2^n-{n-1\choose1}2^{n-2}+{n-2\choose2}2^{n-4}-{n-3\choose3}2^{n-6}+...$$ This identity looks very interesting to me and I am wondering is this expression part of a deeper theorem, where this equivalency is just a manifest of this theorem? Of course one can go backward and prove this identity by expanding $~\dfrac{1}{(1-x)^2}~$ in the two different ways, but I'd like to focus on this identity itself and hope someone can explain it from a different angle (rather than a go-backward-proof).
 A: Short answer. The sequence $a_n = n+1$ satisfies a recurrence $a_n = 2a_{n-1} - a_{n-2}$ which makes it into a Lucas sequence, all of which have a similar formula to the OP's (see below highlighted equation).
For the special case of the Fibonacci sequence, the formula is documented on wikipedia, and has a sort of "combinatorial" proof, in which you show that the formula enumerates a sequence of sets whose cardinalities satisfy the same recurrence. The same idea works for any Lucas sequence (such as the OPs), but it doesn't give a bijective proof the OP might be looking for.
What follows is just a more in depth explanation I wrote while working this out.

Analogy with formula for Fibonacci sequence.
The formula from OP is equivalent to:
$$n+1 = \sum_{k=0}^{n/2} (-1)^k{n-k \choose k}2^{n-2k}$$
and is similar to a formula for the Fibonacci sequence: $$F(n+1) = \sum_{k=0}^{n/2} {n-k\choose k}.$$ This formula has a combinatorial proof by 


*

*interpreting $F(n+1)$ as ways of covering an $n\times 1$ strip with $2\times 1$ and $1\times 1$ tiles.

*counting number of ways using exactly $k$ many $2\times 1$ tiles (and $n-2k$ many $1\times 1$ tiles) to be $ {n -k \choose k}$, because $n-k$ total tiles are used.
Note that Fibonacci sequence has a generating function $x/(1-x-x^2)$, which is similar to $1/(1-2x+x^2)$ which generates $n+1$. 
Another example: Pell numbers.
Similar to the Fibonacci formula is the generating function $1/(1 - 2x - x^2)$ which has formula whose $n$th coefficient is a little closer to what you want:
$$P(n+1) = \sum_{k=0}^{n/2} {n-k \choose k}2^{n-2k}$$
Combinatorially the expression on the right hand side can thought of as adding in colorings (black or white) of the one-by-one tiles. The numbers on the left hand side 1,2,5,12,29,70,169,408,... are the Pell numbers.
In the same spirit as the Fibonacci example you could come up with a "combinatorial" proof of this equality, by showing this set of colored tilings satisfies the recurrence relation $a_{n+1} = 2a_n + a_{n-1}$. This would go something like this: The  new square can be used as a part of a $2\times 1$ tile, or as a $1\times 1$ tile with 2 ways to color it. So, it satisfies the same recurrence as the Pell numbers.
Generalization: Lucas numbers of the second kind. The OP's sequence (aka the positive integers) is a special case of Lucas numbers of the second kind, $U_{n+1}(2,1)$. Fibonacci is $U_n(1,-1)$ and Pell is $U_n(2,-1)$.

In general it seems there is a similar formula for the Lucas numbers of the second kind $U_n(P,Q)$,
  $$U_{n+1}(P,Q) = \sum_{k=0}^{n/2} (-1)^k{n -k \choose k} P^{n-2k}Q^k$$
Note: I didn't check this, I just tested it for a few specific cases of Fibonacci, Pell, Mersenne and OP's $U_n(2,1)$.

If you follow the definition at Mathworld then although it is a degenerate case, you can see that $U_{n+1}(2,1) = n+1$ as
$$U_{n+1}(P,Q) = \frac{a^{n+1} - b^{n+1}}{a-b} = a^nb^0 + a^{n-1}b + \cdots + a^0b^n = n+1$$ for $a,b = 1$.
Just to mimic everything above for Fibonacci/Pell numbers, the sequence $a_{n+1} = 2a_n - a_{n-1}$ (which is solved by integers $n+1 = 2n - (n-1)$) could be counted as the number of colored tilings as before with even number of $2\times1$ tiles minus the number of colored tilings with an odd number of tiles. (It is easy to generalize this to any Lucas sequence!)
