Compute limit by induction ("inductive step of existence" issue)

Question

I was asked to compute the limit $\lim\limits_{x \to 1} \dfrac{\displaystyle\prod_{k=1}^n (1+x^k) - 2^n}{x-1}$

My approach was as follows

i) Define $L(n):=\lim\limits_{x \to 1} \dfrac{\displaystyle\prod_{k=1}^n (1+x^k) - 2^n}{x-1}$

ii) $L(1)$ exists and trying to write $L(n+1)$ in terms of $L(n)$, it turns out that $L(n+1)$ exists iff and $L(n)$ exists (from second line of the following equalities)

$$\begin{align*} L(n+1) & = \lim\limits_{x \to 1} \dfrac{\displaystyle\prod_{k=1}^{n+1} (1+x^k) - 2^{n+1}}{x-1} \\ & = \lim\limits_{x \to 1} \left( 2\times \dfrac{\displaystyle\prod_{k=1}^n (1+x^k) - 2^n}{x-1} + \lim\limits_{x \to 1} \dfrac{x^{n+1}-1}{x-1}\times \prod_{k=1}^n (1+x^k)\right) \\ & = 2L(n) + (n+1)\times 2^n \end{align*}$$

iii) the algebraïc identity linking $L(n)$ and $L(n+1)$ is $L(n+1) = 2L(n) + (n+1)\times2^n$

iv) Then I defined $l(n):=\dfrac{L(n)}{2^n}$ noticing that it satisfies the telescopable relation $l(n+1)-l(n) = \dfrac{n+1}{2}$

v) Computing $l(n)$ then $L(n)$ now is easy and it yields $L(n) = 2^{n-1}\times \dfrac{n(n+1)}{2}$

My question is that a friend objected step (ii) (third line in aligned equations) telling me that the problem of existence is not solved yet the way I did it, and that we can't do such a manipulation when expressions we manipulate are not justified beforehand to exist. As I see it, since $L(1)$ exists and figuring out that $L(n+1)$ exists iff $L(n)$ does, is enough to this issue of existence.

I wonder whether I'm right or wrong and is the proof I provided rigorous enough, otherwise what do I need it to add to get it better

Thanks in advance for any suggestions / advice.

Answer 1

I see nothing wrong with your approach. You proved correctly that:

1. The limit $L(n)$ exists if and only if the limit $L(n+1)$ exists.
2. If both of them exist, then $L(n+1)=2L(n)+(n+1)2^n$.

So, now, since $L(1)$ exists, it's only a matter of using induction to compute the value of $L(n)$ for each $n\in\mathbb N$.

Answer 2

Your ideas are correct.In the second step i would suggest not to take limits because you do not know of the limit in the left hand side exists.Just do the computations of the limits on the right hand side of the equality which we know that exist from the induction hypothesis and etc.

Then after you compute these then you take limits to the left hand side.

using the fact that the limit of $f+gh$ at a point $x_0$ is equal to $\lim f+(\lim g \lim h)$

if $\lim g,\lim f, \lim h$ exist at $x_0$(and are real numbers).

Here it is another proof of the existence with the notion of derivative:

Also to make clear i use just the definition of derivative and not the L'Hospital rule because of the tag.

This limit exists $\forall n\in \mathbb{N}$ because:

Let $n \in \mathbb{N}.$

Take the function $f(x)=\prod_{k=1}^n(1+x^k)$ which is differentiable.

We have that $$\lim_{x \to 1}\frac{\prod_{k=1}^n(1+x^k) -2^n}{x-1}=\lim_{x \to 1}\frac{f(x)-f(1)}{x-1}=f'(1)$$

Now if you want, you can use induction to compute $f'(1)$ as an exercise.

Answer 3

You did right: the proof of existence of $L(n)$, for all $n\ge1$, is good because you know that $L(1)$ exists and that $L(n+1)$ exists as soon as $L(n)$ does.

A different strategy showing the power of differential calculus is to realize that this is the derivative at $1$ of $$ f_n(x)=\prod_{k=1}^n(1+x^k) $$ and that, for $x>0$, $$ \log f_n(x)=\sum_{k=1}^n \log(1+x^k) $$ Hence $$ \frac{f_n'(x)}{f_n(x)}=\sum_{k=1}^n\frac{kx^{k-1}}{1+x^k} $$ and, taking into account that $f_n(1)=2^n$, we get $$ f_n'(1)=2^n\sum_{k=1}^n\frac{k}{2}=2^{n-2}n(n+1) $$ No fancy telescoping and other troubles. I understand you have not yet done derivatives; when you'll have done them, check back and judge for yourself what's the best strategy.

Answer 4

As an alternative, by a combinatorial way, we have that

$$\prod_{k=1}^n (1+x^k) - 2^n =(1+x)(1+x^2)\ldots(1+x^n)-2^n =\overbrace{1+x+x^2+\ldots+x^{\frac{n(n+1)}2}}^{\text{$2^n$ terms}}-2^n=$$

$$=\overbrace{(x-1)+(x^2-1)+\ldots+(x^{\frac{n(n+1)}2}-1)}^{\text{$2^n-1$ terms}}=$$

$$=(x-1)\left(1+(x+1)+(x^2+x+1)+\ldots+(x^{\frac{n(n+1)}2-1}+\ldots+1)\right)=(x-1)\;S(x)$$

and since for $x\to 1$

$$S(x)=1+(x+1)+(x^2+x+1)+\ldots+(x^{\frac{n(n+1)}2-1}+\ldots+1) \to S(1)$$

where $S(1)$ is the sum of all elements of all subsets of $\{1,...,n\}$ which is

$$S(1)= 2^{n-1}\frac{n(n+1)}{2}=2^{n-2}n(n+1)$$

since each number occurs in $2^{n-1}$ subsets, therefore

$$\lim\limits_{x \to 1} \dfrac{\displaystyle\prod_{k=1}^n (1+x^k) - 2^n}{x-1}=\lim\limits_{x \to 1} \frac{(x-1)\;S(x)}{x-1}=\lim\limits_{x \to 1} S(x)=S(1)= 2^{n-2}n(n+1)$$

Answer 5

Write $x\equiv 1+\varepsilon$ then $$ \newcommand{\lime}{\lim_{\varepsilon \rightarrow 0 }\frac1\varepsilon} \lim_{x \rightarrow 1 } \frac{ \prod_{k=1}^n (x^k+1) - 2^n}{x-1} =\lime\left({\prod_{k=1}^n ((1+\epsilon)^k+1)-2^n}\right)\\ =\lime((1+\varepsilon)+1)\left(((1+\varepsilon)^2+1)...((1+\varepsilon)^n+1)-2^n\right)\\ =\lime\left( (2+\varepsilon) (2+2\varepsilon+O(\varepsilon^2))...(2+n\varepsilon+O(\varepsilon^2)))-2^n\right)\\ $$ $$=\lime\left(2^n+2^{n-1}\sum_{i=1}^n i\varepsilon+O(\varepsilon^2)-2^n\right). $$