I would like to prove by induction that the number of arrangements that one can create with A little squares with either two colors (Black or White):
is given by this formula:
$$ a = \sum_{n=0}^A P_A^{A-n,n} $$ Where $$P_A^{A-n,n}:= \frac{A!}{(A-n)!n!}$$
So, there are three steps to prove by induction.
1st Step)
Taking A=1, we have:
$$ a = \sum_{n=0}^1 P_1^{1-n,n} = P_1^{1,0} + P_1^{0,1} = \frac{1!}{1!0!} + \frac{1!}{1!0!} = 1 + 1 = 2 $$
Which is true
2nd Step)
Taking A=k, we have:
$$ a = \sum_{n=0}^k P_k^{k-n,n} $$
3rd Step)
Taking A=k+1, we have:
$$ a = \sum_{n=0}^k P_k^{k-n,n} + 2^{k+1} $$
Could you give me some ideas of How do I make this final step?
Here is a combinatorial argument: The number of ways to arrange $n$ small squares with two colors is $2^n$. $2^n$ is also the number of subsets in a $n$-elements set. The way you think of the $2^n$ formula is that there is two choices for each element in the set to be part of your subset. Since you have $n$ elements, you have $2^n$ choices.
Ok now, the number of subsets can also be partitioned into subset with a specific number of elements ranging from 1,...,n.
Next we show that exactly, the number of subset with j elements in your n element subset is exactly $\frac{n!}{(n-j)!j!}$.
This is because, well, you have n choice for your first element in your subset, n-1 choices for your second element in your subset for a total of $\frac{n!}{(n-j)!}$ choices. But since you are talking about an unordered subset, you have over counted and you need to divide $\frac{n!}{(n-j)!}$ by the number of ways you permute your elements. The number of way to permute $j$ elements is exactly $j!$ and so you get your formula $\frac{n!}{(n-j)!j!}$. Ok, so that counts the number of subset with $j$ elements and you need to sum over all possible $j \in \{0,...,n\}$.
Ok so for the inductive proof, You can just do $2*\sum_{i=0}^kP_k^{i,k-i}=2*2^k=2^{k+1}=\sum_{i=0}^{k+1}P_{k+1}^{i,k+1-i}$