Given $x\odot y=x+y+xy$, prove $x\odot x\odot\ldots\odot x= (1+x)^n -1$

Question

Given $x\odot y=x+y+xy$, prove that $$\underbrace{x\odot x\odot\ldots\odot x}_{n\text{ times}}= (1+x)^n -1$$ for all $n\in \Bbb{N}$ and $x \in\Bbb R\setminus\{-1\}$.

I have tried to use the binomial theorem on $(1+x)^n$ but was unable to simplify the nested function. Also tried mathematical induction but that didn't work out. The nested function is still stumping me as I haven't figured out how to generalize it for $n$ terms. Also some information on how to deal with nested functions would be greatly appreciated.

Answer 1

By induction: $$x_1 = x$$ $$x_n = x \odot x_{n-1} = x+x_{n-1} + xx_{n-1} \Rightarrow \\ x_n = (1+x)x_{n-1} + x.$$

Then: $$x_n = (1+x)\left[(1+x)x_{n-2} + x\right] + x = \\ = (1+x)^2x_{n-2} + (1+x)x + x = \\ = (1+x)^3x_{n-3} + (1+x)^2x + (1+x)x + x \Rightarrow\\ x_n = (1+x)^{h}x_{n-h}+x\sum_{k=0}^{h-1} (1+x)^k.$$

For $h=n-1$:

$$x_n = (1+x)^{n-1}x_{1}+x\sum_{k=0}^{n-2} (1+x)^k \Rightarrow \\ x_n = (1+x)^{n-1}x + x\frac{1-(1+x)^{n-1}}{1-(1+x)} \Rightarrow \\ x_n = (1+x)^{n-1}x - (1-(1+x)^{n-1}) \Rightarrow \\ x_n = (1+x)^{n-1}(1+x) - 1 \Rightarrow\\ x_n = (1+x)^n - 1.$$

Answer 2

Have you tried induction? For $n\rightarrow n+1$, you have \begin{align} &[(1+x)^n-1]\circ x\\ =&((1+x)^n-1)x+((1+x)^n-1)+x\\ =&(1+x)^nx+(1+x)^n-1\\ =&(1+x)^{n+1}-1. \end{align}

Answer 3

Hint : $1+x\odot y=1+x+y+xy=(1+x)(1+y)$.