6
$\begingroup$

I oversaw a high-school mathematics test the other day, and one of the problems was the following

Show, using induction or other means, that $$\sum_{i = 1}^n\frac1{i(i+1)} = 1-\frac1{n+1}$$

The induction proof is very standard, where the induction step relies on the fact that $\frac{1}{n+1} + \frac{1}{n(n+1)} = \frac{1}{n}$, and I'm sure it's been answered on this site before. However, I got intrigued by the "or other means" part of the question.

I don't know whether the teacher who wrote the test even considered any alternative solutions (he may just have written it so that if anyone has a crazy idea that works out, then they should get a full score for it), but I tried to find one. For instance, we may do the following telescope-ish argument: $$ \frac{1}{1(1+1)} + \frac{1}{2(2+1)} + \cdots + \frac{1}{(n-1)n} + \frac{1}{n(n+1)} + \frac{1}{n+1}\\ = \frac{1}{1(1+1)} + \frac{1}{2(2+1)} + \cdots + \frac{1}{(n-1)n} + \frac1n\\ \vdots\\ = \frac{1}{1(1+1)} + \frac12\\ = 1 $$ However, I feel that this is just an induction proof in disguise (hidden in the vertical dots). If one uses the mechanics of the induction proof to check whether the formula is true for a specific $n$, then one certainly does the exact same calculations as I have done here.

Is there a proof of this fact that clearly does not use induction (or at least hides it better)? The more elementary the better, and the ultimate goal would be to do it within the syllabus of the students taking the test (or at least not far from it). For reference, they should be familiar with the summation formula of arithmetic and geometric series and their derivations (so techniques resembling those would be well within specifications).

If there is a solution using calculus, then the students should be able to integrate elementary trigonometric functions, as well as exponential functions, logarithms and rational functions. They are familiar with integration by parts, substitution and partial fractions.

I welcome more advanced solutions as well, of course.

$\endgroup$
  • 2
    $\begingroup$ @JonWarneke But if you work your way up from the bottom "$=1$" to the top row in the telescoping sum, then you retrace exactly the steps in the inductive proof when passing through the vertical dots. That's what I meant by "induction in disguise". $\endgroup$ – Arthur Apr 14 '16 at 20:11
  • 1
    $\begingroup$ @openspace He is trying to avoid telescoping or induction I believe. $\endgroup$ – Simply Beautiful Art Apr 14 '16 at 20:14
  • 1
    $\begingroup$ Note that here, $$a_i = \frac{1}{i(i+1)} = \frac{i+1-1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1} $$ so that summing up the $a_i$s leaves out only $1-\frac{1}{n+1}$ as desired. $\endgroup$ – Aritra Das Apr 14 '16 at 20:14
  • 3
    $\begingroup$ @AritraDas I've been disliking "without induction" proofs more and more because the fact of the matter is in induction is ALWAYS present, almost by definition of "Mathematics". So how deep does induction need to be hidden for a proof to be regarded as "without induction"? And how does one even define "depth" here? Long story short, disregard my comment, I don't think the question can be answered. $\endgroup$ – Git Gud Apr 14 '16 at 20:24
  • 1
    $\begingroup$ @GitGud Sh, don't say that just yet man! $\endgroup$ – Simply Beautiful Art Apr 14 '16 at 20:25
7
$\begingroup$

You can use a partial fractions decomposition, which assumes that we can rewrite $$ \frac{1}{i(i+1)} = \frac{A}{i} + \frac{B}{i+1}, \qquad 1 \leq i \leq n $$ for some $A, B$. Clearing denominators, the above equation is $1 = A(i+1) + B i$ for $1 \leq i \leq n$ which has solution $A=1$, $B=-1$. Hence \begin{align*} \sum_{i=1}^n \frac{1}{i(i+1)} &= \sum_{i=1}^n \frac{1}{i} - \frac{1}{i+1} \\ &= \left(1 \color{red}{- \frac{1}{2}} \right) + \left(\color{red}{\frac{1}{2}} \color{orange}{- \frac{1}{3}} \right) + \left(\color{orange}{\frac{1}{3}} \color{green}{- \frac{1}{4}} \right) + \cdots + \left(\color{blue}{\frac{1}{n-1}} \color{purple}{- \frac{1}{n}} \right) + \left( \color{purple}{\frac{1}{n}} - \frac{1}{n+1} \right) \\ &= 1 - \frac{1}{n+1}. \end{align*}

All adjacent (colored) summands cancel each other except for $1$ and $-\frac{1}{n+1}$, so we're left with $1 - \frac{1}{n+1}$. There's nothing inductive about it. It's just a convenient finite sum.

$\endgroup$
  • 2
    $\begingroup$ This is the solution I should've seen myself (as I said in the comments). It does exactly the same telescoping as in the inductive proof, but does all of them at once, thus removing the "one-at-a-time" feel of the original inductive proof. I think this is as good as it gets, dince (as noted by GitGud in the comments) if this isn't induction free, then what is? $\endgroup$ – Arthur Apr 14 '16 at 20:44
5
$\begingroup$

For a proof of intermediate level, note that for each $k=1,2....,n$ we have $$\int_k^{k+1} \frac{1}{t^2}\ dt=\frac{1}{k(k+1)}.$$ Adding these integrals for $k$ from $1$ to $n$ then gives $$\int_1^{n+1}\frac{1}{t^2}\ dt=1-\frac{1}{n+1}.$$

In this approach the "telescoping" may be said to hide in the additivity of the integral over the disjoint subintervals of $[1,n+1].$

$\endgroup$
4
$\begingroup$

You can write $$ \sum_{i = 1}^n\frac1{i(i+1)} = \sum_{i = 1}^n\left[\frac{1}{i}-\frac{1}{i+1}\right]\ . $$ Then use the identity $$ \frac{1}{x}=\int_0^\infty ds e^{-s x}\qquad x>0\ , $$ to write $$ \sum_{i = 1}^n\left[\frac{1}{i}-\frac{1}{i+1}\right]=\int_0^\infty ds\sum_{i=1}^n \left[e^{-s i}-e^{-s (i+1)}\right]\ , $$ and then use geometric sums $$ \int_0^\infty ds \left[e^{-s}-e^{-(n+1) s}\right]=\frac{n}{n+1}\ . $$

$\endgroup$
  • $\begingroup$ This is a very cool solution, and the best ones in the class should definitely be able to follow it, even if it might be beyond all but very few on that level to come up with it. $\endgroup$ – Arthur Apr 14 '16 at 20:47
2
$\begingroup$

You can use finite difference method to solve this (although, it truly shines with more complex sums, and is an overkill here).

Define $(\Delta f)(x)$ as $f(x+1)-f(x)$ It's easy to see that operator $\Delta$ is linear. It's supposed to be similar to differential operator, and recall that $D(x^k) = kx^{k-1}$, here we have a similar fact, but not for standard power, but for falling factorial instead.

Define falling factorial of x to be $$(x)_n =\begin{cases}x(x-1)(x-2)\ldots(x-n+1)& n>0\\ 1 & n = 0\\ \frac{1}{(x+1)(x+2)\ldots(x+n)}& n < 0 \end{cases}$$

This operation is defined in such a way, to satisfy for all $n,m\in\mathbb{Z}$ the property $(x)_{m+n}=(x)_m(x-m)_n$
Moreover $\Delta((x)_n) = (x+1)_n - (x)_n = (x+1)x(x-1)\ldots(x-n+2) - x(x-1)\ldots(x-n+1) = x(x-1)\ldots(x-n+2)(x+1 - (x-n+1)) = n(x)_{n-1}$
I am only proving this property for positive $n$, but it holds in general.

Now, let's move one to sums. Define the $\Sigma$ operator to be
$$\sum g(x)\delta x = f(x) + p(x) \iff g(x) = \Delta f(x)$$ Where $p$ denotes a function satisfying $p(x+1)=p(x)$ (such functions vanish under $\Delta$ operator).

And let $\sum_a^b g(x)\delta x = f(b) - f(a)$ It is clear, that this new kind of sum is directly connected to standard summation - indeed $\sum_a^bg(x) \delta x = \sum_{k=a}^{b-1}g(k)$, which is obvious enough given that $\sum_a^a g(x) \delta x = f(a) - f(a) = 0$ and
$\sum_a^{b+1}g(x)\delta x - \sum_a^b g(x) \delta x = (f(b+1)-f(a)) - (f(b)-f(a)) = f(b+1) - f(b) = g(b)$

So, in our new notation, the sum in question can be rewritten as $$\sum_{k=1}^n \frac{1}{k(k+1)} = \sum_{0}^{n} (x)_{-2}\delta x$$

Just like in calculus, remembering our remark about $\Delta$ of falling factorial we arrive at equation $$\sum (x)_n \delta x = \frac{(x)_{n+1}}{n+1} + C \hspace{10pt} \text{for } n \not= -1$$

So we have $\sum (x)_{-2}\delta x = -(x)_{-1} + C$ Plugging that into our formula we arrive at
$$\sum_{0}^{n}(x)_{-2}\delta x = -(n)_{-1} - (-(0)_{-1}) = 1- \frac{1}{n+1}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.