Summation of Double Exponential Series [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Is there any known closed form or tight bound analysis (big-O or big-$Theta$) for $sum_i = 0^n 2^2^i$?
sequences-and-series summation exponential-sum summation-method
asked Aug 17 at 1:17
Nima
32
closed as off-topic by Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson Aug 19 at 0:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson
add a comment |Â
up vote
0
down vote
favorite
Is there any known closed form or tight bound analysis (big-O or big-$Theta$) for $sum_i = 0^n 2^2^i$?
sequences-and-series summation exponential-sum summation-method
asked Aug 17 at 1:17
Nima
32
closed as off-topic by Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson Aug 19 at 0:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Is there any known closed form or tight bound analysis (big-O or big-$Theta$) for $sum_i = 0^n 2^2^i$?
sequences-and-series summation exponential-sum summation-method
asked Aug 17 at 1:17
Nima
32
Is there any known closed form or tight bound analysis (big-O or big-$Theta$) for $sum_i = 0^n 2^2^i$?
sequences-and-series summation exponential-sum summation-method
asked Aug 17 at 1:17
Nima
32
asked Aug 17 at 1:17
Nima
32
asked Aug 17 at 1:17
Nima
32
asked Aug 17 at 1:17
Nima
32
32
closed as off-topic by Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson Aug 19 at 0:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson
closed as off-topic by Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson Aug 19 at 0:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Sil, Andres Mejia, amWhy, Xander Henderson
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
It is true that
$$
2^2^nle sum_i=0^n 2^2^ile 2^2^n+sum_k=0^2^n-12^k=2^2^n+2^2^n-1+1-1le 2^2^n+2cdot 2^2^n-1=2^2^n(1+2cdot 2^-2^n-1)
$$
This shows that your sum is eventually between $2^2^n$ and $(1+epsilon)2^2^n$ for any $epsilon>0$.
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
add a comment |Â
up vote
3
down vote
If within constants is fine, then here's an easy proof that it is $Theta(2^2^n)$. The idea is that $2^2^i$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.
The lower bound is obvious. For the upper bound, we show that $sum_i=1^n 2^2^ileq 2cdot 2^2^n$ by induction. Start with the inductive hypothesis. Then,
beginalign*
sum_i=1^n 2^2^i &leq 2cdot 2^2^nleq 2^2^ncdot 2^2^n = 2^2^n+1.
endalign*
Now adding $2^2^n+1$ on both sides allows us to conclude as desired.
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
It is true that
$$
2^2^nle sum_i=0^n 2^2^ile 2^2^n+sum_k=0^2^n-12^k=2^2^n+2^2^n-1+1-1le 2^2^n+2cdot 2^2^n-1=2^2^n(1+2cdot 2^-2^n-1)
$$
This shows that your sum is eventually between $2^2^n$ and $(1+epsilon)2^2^n$ for any $epsilon>0$.
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
add a comment |Â
up vote
2
down vote
accepted
It is true that
$$
2^2^nle sum_i=0^n 2^2^ile 2^2^n+sum_k=0^2^n-12^k=2^2^n+2^2^n-1+1-1le 2^2^n+2cdot 2^2^n-1=2^2^n(1+2cdot 2^-2^n-1)
$$
This shows that your sum is eventually between $2^2^n$ and $(1+epsilon)2^2^n$ for any $epsilon>0$.
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
It is true that
$$
2^2^nle sum_i=0^n 2^2^ile 2^2^n+sum_k=0^2^n-12^k=2^2^n+2^2^n-1+1-1le 2^2^n+2cdot 2^2^n-1=2^2^n(1+2cdot 2^-2^n-1)
$$
This shows that your sum is eventually between $2^2^n$ and $(1+epsilon)2^2^n$ for any $epsilon>0$.
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
It is true that
$$
2^2^nle sum_i=0^n 2^2^ile 2^2^n+sum_k=0^2^n-12^k=2^2^n+2^2^n-1+1-1le 2^2^n+2cdot 2^2^n-1=2^2^n(1+2cdot 2^-2^n-1)
$$
This shows that your sum is eventually between $2^2^n$ and $(1+epsilon)2^2^n$ for any $epsilon>0$.
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
answered Aug 17 at 1:58
Mike Earnest
16.6k11748
16.6k11748
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
add a comment |Â
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
Thanks a lot. Just a follow-up question: by any $epsilon > 0$, you mean that for any such parameter, there as a large enough $n$, right?
– Nima
Aug 17 at 18:26
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
@Nima That is correct. The time you have to wait depends on $epsilon$. Specifically, you need $nge log log frac1epsilon$.
– Mike Earnest
Aug 17 at 18:28
add a comment |Â
up vote
3
down vote
If within constants is fine, then here's an easy proof that it is $Theta(2^2^n)$. The idea is that $2^2^i$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.
The lower bound is obvious. For the upper bound, we show that $sum_i=1^n 2^2^ileq 2cdot 2^2^n$ by induction. Start with the inductive hypothesis. Then,
beginalign*
sum_i=1^n 2^2^i &leq 2cdot 2^2^nleq 2^2^ncdot 2^2^n = 2^2^n+1.
endalign*
Now adding $2^2^n+1$ on both sides allows us to conclude as desired.
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
add a comment |Â
up vote
3
down vote
If within constants is fine, then here's an easy proof that it is $Theta(2^2^n)$. The idea is that $2^2^i$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.
The lower bound is obvious. For the upper bound, we show that $sum_i=1^n 2^2^ileq 2cdot 2^2^n$ by induction. Start with the inductive hypothesis. Then,
beginalign*
sum_i=1^n 2^2^i &leq 2cdot 2^2^nleq 2^2^ncdot 2^2^n = 2^2^n+1.
endalign*
Now adding $2^2^n+1$ on both sides allows us to conclude as desired.
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
add a comment |Â
up vote
3
down vote
up vote
3
down vote
If within constants is fine, then here's an easy proof that it is $Theta(2^2^n)$. The idea is that $2^2^i$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.
The lower bound is obvious. For the upper bound, we show that $sum_i=1^n 2^2^ileq 2cdot 2^2^n$ by induction. Start with the inductive hypothesis. Then,
beginalign*
sum_i=1^n 2^2^i &leq 2cdot 2^2^nleq 2^2^ncdot 2^2^n = 2^2^n+1.
endalign*
Now adding $2^2^n+1$ on both sides allows us to conclude as desired.
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
If within constants is fine, then here's an easy proof that it is $Theta(2^2^n)$. The idea is that $2^2^i$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.
The lower bound is obvious. For the upper bound, we show that $sum_i=1^n 2^2^ileq 2cdot 2^2^n$ by induction. Start with the inductive hypothesis. Then,
beginalign*
sum_i=1^n 2^2^i &leq 2cdot 2^2^nleq 2^2^ncdot 2^2^n = 2^2^n+1.
endalign*
Now adding $2^2^n+1$ on both sides allows us to conclude as desired.
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
answered Aug 17 at 1:41
Taisuke Yasuda
1,682212
1,682212
add a comment |Â
add a comment |Â
