6
$\begingroup$

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?

Thanks for your help.

  • 3
    **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$.2012-08-30

2 Answers 2

3

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$.

  • 0
    Very nice solution. I am reading the PDF. Thanks for your help2012-08-31
1

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.

  • 0
    Oh, I didn't try to compare with $H(n+1)-H(n)$ and $H(n)-H(n-1)$.2012-08-31