Suggestion to solve the equation: $$T(n)=2T(n-1)+\frac{1}{n}+1?$$
Asked
Active
Viewed 80 times
-1
-
Are you sure this simplification is correct? – SL_MathGuy Jan 22 '20 at 00:40
-
According to Wolfram Alpha, $$ T(n) = 2^n\log 2 - \sum_{k=0}^\infty\frac{(1/2)^{k+1}}{n+k+1}. $$ – Math1000 Jan 22 '20 at 00:53
-
OEIS A068102 is $n!, T(n)$ and does not suggest a closed form – Henry Jan 22 '20 at 00:56
-
All of your questions are closed. In order to avoid this, please see How to ask a good question and try to avoid problem statement questions. This means including more than just the problem in the post. Where did it come from? What are you struggling with? What have you done? Note that this is not a homework solving site, you are expected to bring a bit to the conversation yourself. – Simply Beautiful Art Jan 26 '20 at 02:07
2 Answers
1
$$T(n) = 2. T(n-1) + \dfrac{1}{n}$$
$$T(n) - 2. T(n-1) = \dfrac{1}{n}$$.
Divide both sides by $2^{n-1}$, we get,
$$\dfrac{T(n)}{2^{n-1}}-\dfrac{T(n-1)}{2^{n-2}} = \dfrac{1}{n.2^{n-1}}$$
Let $g(n) =\dfrac{T(n)}{2^{n-1}}$. Then, the above equation can be rewritten of the form,
$$g(n) - g(n-1) = \dfrac{1}{n.2^{n-1}}.$$ Summing this from $n=2$ to $n=k$, we get,
$$g(k) - g(1) = \sum_{n=2}^{k} \dfrac{1}{n.2^{n-1}}.$$ So,
$$g(k) = g(1) + \sum_{n=2}^{k} \dfrac{1}{n.2^{n-1}}. $$ $g(1)$ can be found using $T(1)$. Hence,you can obtain the equation for $T(k)$.
NOTE: $\sum_{n=2}^{\infty} \dfrac{1}{n.2^{n-1}}$ converges.
Consider $\sum \dfrac{x^n}{n}$. Then, $$\dfrac{d(\sum\dfrac{x^n}{n})}{dx} = \sum_{n \geq 1}x^{n-1}.$$ We know $\sum x^n = \dfrac{1}{1-x}$ for $|x|<1$. So, $\sum \dfrac{x^n}{n} = - log(1-x)$. In your case, just plug in $x=1/2$.
SL_MathGuy
- 1,574
-
Thanks for the reply. Could you please explain a bit more on the steps where you considered $∑x^n/n$ and onwards? Specifically: a)why did you considered the summation $∑x^n/n$? b)what does differentiating the summation $∑x^n/n$ means? c)how did you arrive $∑x^n/n = -log(1-x)$ from $∑x^n = 1/(1-x)$? – Polycom Jan 22 '20 at 09:06
-
@Polycom My idea was to prove $\sum \frac{1}{n2^{n-1}}$ converges. In order to do that, I considered $\sum \frac{x^n}{n}$ (because when $x=1/2$, this becomes our desired series). In order to evaluate $\sum \frac{x^n}{n}$, I considered $\sum x^n$ since $\frac{d( \frac{x^n}{n})}{dx} = \sum_{n \geq 0} x^n$.
We know, $\sum x^n = \frac{1}{1-x}$ (for $|x|<1$). Hence, $\sum \frac{x^n}{n}= \int \sum x^n = \int \frac{1}{1-x} = -log(1-x) $.
Once you plug in $x=1/2$, you have $\sum_{n=1}^{\infty} \frac{1}{n2^n} = log 2$
– SL_MathGuy Jan 22 '20 at 22:20
0
I'd rather rewrite it as
$$T(n)=2^{n-1}+2^n\sum_{k=2}^n\frac1{k2^k}$$
where $j=n-k$. Now notice that we have
$$\sum_{k=2}^n\frac1{k2^k}\le\sum_{k=2}^\infty\frac1{2^k}=\frac12$$
and hence
$$T(n)\le2^n\implies T(n)\in\mathcal O(2^n)$$
As far as closed form goes, you can rewrite this in terms of the Lerch transcendent:
$$T(n)=2^n\ln(2)-\frac12\Phi\left(\frac12,1,n+1\right)$$
Simply Beautiful Art
- 74,685