# prove by induction : $\frac{(1-a^n)}{1-a}+\frac{(1-a^n)(1-a^{n-1})}{1-a^2}+…+\frac{(1-a^n)(1-a^{n-1})…(1-a)}{1-a^n}=n$

How to prove the following question by using induction?

$${\frac{(1-a^n)}{1-a}+\frac{(1-a^n)(1-a^{n-1})}{1-a^2}+\frac{(1-a^n)(1-a^{n-1})(1-a^{n-2})}{1-a^3}+...+\frac{(1-a^n)(1-a^{n-1})...(1-a)}{1-a^n}=n}$$

and I am interested in solutions without using Induction. Can anyone show me the steps?

-
+1 Nice question! But you could possibly make it more explicit: do you want a proof by induction, or without using induction? The title seems to contradict the request in the body of the post. –  Sasha Aug 30 '12 at 19:38
Above your expression for $n$, write down the expression for $n+1$. Subtract. Simplify the terms which have the same denominator. They simplify lots, the denominator disappears. There is a dangling term on top. Add it in. We get $1$. –  André Nicolas Aug 30 '12 at 21:11

Historical digression
In the paper "Consideration of Some Series Which Are Distinguished by Special Properties", published in 1753, Leonhard Euler consider the following series (see MAA editorial "How Euler Did It" on "False Log Series", pdf): $$s_a(x) = \sum_{n=1}^\infty \frac{1}{1-a^n} \prod_{k=0}^{n-1}\left(1-\frac{x}{a^k}\right)$$ Notice the series terminates for $x=a^{m}$, where $m\in \mathbb{N}$ and becomes exactly the series in the OP.

Euler showed, that both $s_a(a^m) = m = \log_a(a^m)$, but that $s_a(x)$ is different from $\log_a(x)$ in general (see my Wolfram demonstration for a visual comparison).

Solving the recurrence equation
Consider the recurrence equation, derived by @Mathlover: $$f_a(n) (1-a^n) = f_a(n+1) - a^n$$ where $f_a(n) = H_a(n)-H_a(n-1)$. Being a recurrence equation of the degree one, we can write its general solution easily, rewriting as : $$\left(f_a(n)-1\right)(1-a^n) = \left(f_a(n_1)-1\right)$$ meaning that $$f_a(n) = 1 + (f_a(1)-1) \prod_{k=1}^{n-1} \left(1-a^k\right)$$ With the given initial condition of $f_a(1) = 1$, the solution is $f_a(n) = 1$, implying that $H_a(n) = n$.

-
+1 for nice solution. Great –  Mathlover Aug 30 '12 at 23:12
Very nice solution. I am reading the PDF. Thanks for your help –  cwk709394 Aug 31 '12 at 11:14

I applied Andre Nicolas's method. Please see steps below. $$H_a(n)=\frac{(1-a^n)}{1-a}+\frac{(1-a^n)(1-a^{n-1})}{1-a^2}+\frac{(1-a^n)(1-a^{n-1})(1-a^{n-2})}{1-a^3}+...+\frac{(1-a^n)(1-a^{n-1})...(1-a)}{1-a^n}$$

$$H_a(n+1)=\frac{(1-a^{n+1})}{1-a}+\frac{(1-a^{n+1})(1-a^{n})}{1-a^2}+\frac{(1-a^{n+1})(1-a^{n})(1-a^{n-1})}{1-a^3}+...+\frac{(1-a^{n+1})(1-a^{n})...(1-a)}{1-a^{n+1}}$$

$$H_a(n+1)-H_a(n)=a^n+a^{n-1}(1-a^n)+a^{n-2}(1-a^n)(1-a^{n-1})+...+\frac{(1-a^{n+1})(1-a^{n})...(1-a)}{1-a^{n+1}}$$

$$H_a(n)-H_a(n-1)=a^{n-1}+a^{n-2}(1-a^{n-1})+a^{n-3}(1-a^{n-1})(1-a^{n-2})+...+\frac{(1-a^{n})(1-a^{n-1})...(1-a)}{1-a^{n}}$$

$$(1-a^n)(H_a(n)-H_a(n-1))+a^n=a^n+a^{n-1}(1-a^n)+a^{n-2}(1-a^n)(1-a^{n-1})+a^{n-3}(1-a^n)(1-a^{n-1})(1-a^{n-2})+...+(1-a^n)\frac{(1-a^{n})(1-a^{n-1})...(1-a)}{1-a^{n}}$$

$$(1-a^n)(H_a(n)-H_a(n-1))+a^n=H_a(n+1)-H_a(n) \tag1$$

If we select $H_a(n)=n+c$ (where c is constant), $H_a(n)=n+c$ satisfies Equation (1).

But we know that $H_a(1)=\frac{(1-a^1)}{1-a}=1$, so $c$ should be zero

Note: I could not find a method to solve Equation (1) and to find the solution directly $H_a(n)=n+c$. If someone knows how to prove that I will be happy to see it.

-
+1 The equation turns out to be easy to solve (see my post). –  Sasha Aug 30 '12 at 22:57
Oh, I didn't try to compare with $H(n+1)-H(n)$ and $H(n)-H(n-1)$. –  cwk709394 Aug 31 '12 at 11:19