Proof for the general formula for $a^n+b^n$.

Question

Based on the following observations. That is

$$a+b = (a+b)^1 \\ a^2+b^2 = (a+b)^2-2ab \\ a^3+b^3 = (a+b)^3-3ab(a+b) \\ a^4+b^4= (a+b)^4-4ab(a+b)^2+2(ab)^2\\ a^5+b^5 = (a+b)^5 -5ab(a+b)^3+5(ab)^2(a+b)\\\vdots$$

I came to make the following conjecture as general formula.

$$ a^n +b^n =\sum_{k=0}^{n-1}(-1)^k \frac{n\Gamma(n-k)}{\Gamma(k+1)\Gamma(n-2k+1)}(a+b)^{n-2k}(ab)^k $$ where $\Gamma(.) $ is gamma function.

I tried up proving the result using binomial theorem $\displaystyle (a+b)^n=\sum_{r=0}^n a^{n-r}b^r$ for positive integers $a,b$ however, I didn't find any elegance in the work. So in the expect of some beautiful proofs, I wish to share general formula here.

Thank you

Answer 1

$a$ and $b$ are roots of $x^2=(a+b)x-ab$. Therefore, $a^{n+2}=(a+b)a^{n+1}-(ab)a^n$ and analogously for $b$.

Let $p_n=a^n+b^n$. Then $p_{n+2}=(a+b)p_{n+1}-(ab)p_n$ is a simple recurrence. The initial values are of course $p_0=2$ and $p_1=a+b$.

This recurrence is a special case of Newton's identities.

Answer 2

You want to express $x^n+b^n$ in terms of their sum, or (for convenience) half-sum $s:=\dfrac{a+b}2$, and geometric mean $p:=\sqrt{ab}$.

We have

$$2as=a^2+ab=a^2+p^2,$$ giving

$$a=s\pm\sqrt{s^2-p^2},b=s\mp\sqrt{s^2-p^2}.$$

Now

$$a^n+b^n=\sum_{k=0}^n\binom nk\left(s^{n-k}(s^2-p^2)^{k/2}+(-1)^ks^{n-k}(s^2-p^2)^{k/2}\right) \\=2\sum_{j=0}^{2j\le n}\binom n{2j}s^{n-2j}(s^2-p^2)^j.$$

This further expands as

$$2\sum_{j=0}^{2j\le n}\binom n{2j}s^{n-2j}(s^2-p^2)^j =2\sum_{j=0}^{2j\le n}\binom n{2j}s^{n-2j}\sum_{i=0}^j\binom ji(-1)^is^{2(j-i)}p^{2i} \\=2s^n\sum_{j=0}^{2j\le n}\sum_{i=0}^j(-1)^i\binom n{2j}\binom ji\left(\frac ps\right)^{2i}.$$

Some more work is needed to regroup the terms by equal $i$.

Answer 3

Let $|\mathbb{A}|=a$ be an alphabet on $a$ letters and let $|\mathbb{B}|=b$ be an alphabet in $b$ letters. Notice that the left hand side $a^n+b^n$ is the number of strings of length $n$ with either all letters in $\mathbb{A}$ or all letters in $\mathbb{B}.$ Let $\mathcal{C}=\{x\in (\mathbb{A}\cup \mathbb{B})^n:\text{x contains letters from both alphabets}\}$ then $a^n+b^n=(a+b)^n-|\mathcal{C}|.$ Now consider $$\mathcal{C}=\bigcup _{i=1}^{n-1}A_i,$$ where $A_i=\{x\in (\mathbb{A}\cup \mathbb{B})^n:x_i \text{ and }x_{i+1}\text{ are not in the same alphabet}\}$ then using inclusion-exclusion you get that $$|\mathcal{C}|=\sum _{i=1}^{n-1}(-1)^{i-1}\sum _{X\in \binom{[n-1]}{i}}|\bigcap _{x\in X}A_x|.$$ Notice that $|A_i|=(a+b)^{n-2}(ab)^1$ and in general $|\bigcap _{x\in X} A_x|=(a+b)^{n-2|X|}(ab)^X$ because you are free to choose the alphabet in $n-2k$ positions and you have to alternate in $2k$ positions($a^k$ for half and $b^k$ for half) and so plugging in the equation and noticing that you do not want to repeat index(so taking consecutive indices) because you would be overcounting (so instead of the usual $\binom{n-1}{i},$ you get $\binom{n-i-1}{i-1}+\binom{n-i}{i}=\frac{n}{n-i}\binom{n-i}{i}$ depending on if you want the last letter to be alternative or no) we get that $$a^n+b^n=(a+b)^n-\sum _{i=1}^{n-1}(-1)^{i-1}\frac{n}{n-i}\binom{n-i}{i}(a+b)^{n-2i}(ab)^i=\sum _{i=0}^{n-1}(-1)^i\frac{n}{n-i}\binom{n-i}{i}(a+b)^{n-2i}(ab)^i.$$

This fits in the Combinatorial interpretation of the Chebyshev polynomials (commented above by Professor Vector). See, for example, Counting on Chebyshev Polynomials, A. Benjamin and D. Walton