Mixing
How to show this inequality involving generalized Fibonacci sequence?
$begingroup$
Define recursively,
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that
$$lim_{nto infty}frac{f(n+1,k)}{f(n,k)}=phi(k)$$
where $phi(k)>0$ is the positive root of the polynomial
$$g_k(x) = x^{k}-sum_{0leq l< k}x.$$
Then I observed that,
$$lim_{kto infty} phi(k)=2.$$
I intend to prove this fact by showing that
$$2(1-2^{-k})<phi(k)<2.$$
I understand why $phi(k)<2$ since $g_k(2)=1.$ But I am not sure why
$$2(1-2^{-k})<phi(k)$$
holds. I have shown that
$$phi(k)<phi(k+1)$$
perhaps this helps in proving this inequality. I don't know. Any ideas to prove the inequality will be much appreciated.
inequality recurrence-relations fibonacci-numbers
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
$endgroup$
add a comment |
$begingroup$
Define recursively,
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that
$$lim_{nto infty}frac{f(n+1,k)}{f(n,k)}=phi(k)$$
where $phi(k)>0$ is the positive root of the polynomial
$$g_k(x) = x^{k}-sum_{0leq l< k}x.$$
Then I observed that,
$$lim_{kto infty} phi(k)=2.$$
I intend to prove this fact by showing that
$$2(1-2^{-k})<phi(k)<2.$$
I understand why $phi(k)<2$ since $g_k(2)=1.$ But I am not sure why
$$2(1-2^{-k})<phi(k)$$
holds. I have shown that
$$phi(k)<phi(k+1)$$
perhaps this helps in proving this inequality. I don't know. Any ideas to prove the inequality will be much appreciated.
inequality recurrence-relations fibonacci-numbers
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
$endgroup$
add a comment |
$begingroup$
Define recursively,
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that
$$lim_{nto infty}frac{f(n+1,k)}{f(n,k)}=phi(k)$$
where $phi(k)>0$ is the positive root of the polynomial
$$g_k(x) = x^{k}-sum_{0leq l< k}x.$$
Then I observed that,
$$lim_{kto infty} phi(k)=2.$$
I intend to prove this fact by showing that
$$2(1-2^{-k})<phi(k)<2.$$
I understand why $phi(k)<2$ since $g_k(2)=1.$ But I am not sure why
$$2(1-2^{-k})<phi(k)$$
holds. I have shown that
$$phi(k)<phi(k+1)$$
perhaps this helps in proving this inequality. I don't know. Any ideas to prove the inequality will be much appreciated.
inequality recurrence-relations fibonacci-numbers
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
$endgroup$
Define recursively,
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that
$$lim_{nto infty}frac{f(n+1,k)}{f(n,k)}=phi(k)$$
where $phi(k)>0$ is the positive root of the polynomial
$$g_k(x) = x^{k}-sum_{0leq l< k}x.$$
Then I observed that,
$$lim_{kto infty} phi(k)=2.$$
I intend to prove this fact by showing that
$$2(1-2^{-k})<phi(k)<2.$$
I understand why $phi(k)<2$ since $g_k(2)=1.$ But I am not sure why
$$2(1-2^{-k})<phi(k)$$
holds. I have shown that
$$phi(k)<phi(k+1)$$
perhaps this helps in proving this inequality. I don't know. Any ideas to prove the inequality will be much appreciated.
inequality recurrence-relations fibonacci-numbers
inequality recurrence-relations fibonacci-numbers
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
asked Jan 12 at 14:35
Hello_WorldHello_World
4,13121831
4,13121831
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $phi(1)=1=2(1-2^{-1})$. Here equality holds.
Let us thus suppose $k geq 2$. Then $g_k(1)=1-k neq 0$ so $phi(k) neq 1$. Now $phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, frac{2k}{k+1}]$ and decreasing on $[frac{2k}{k+1},infty]$. We have $p(1)=0, p(2)=-1$.
Remark: If we just wanted to prove the weaker statement $lim_{kto infty} phi(k)=2$, note that we clearly have $phi(k) in (frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.
Note $2^k=(1+1)^k geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) geq 2(1-frac{1}{k+1})=frac{2k}{k+1}$. Finally
$$
begin{align}
p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \
&=2(1-2^{-k})^k-1 \
& >2(1-k2^{-k})-1 \
&=1-frac{k}{2^{k-1}} \
& geq 0 \
end{align}$$
where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.
Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,frac{2k}{k+1}]$, $p(x) geq p(2(1-2^{-k}))>0$ on $[frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) leq p(2)<0$ on $[2,infty)$. Thus we conclude $phi(k) in (2(1-2^{-k}), 2)$.
Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $phi(k) in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.
answered Jan 12 at 16:02
user634090user634090
262
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3070958%2fhow-to-show-this-inequality-involving-generalized-fibonacci-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $phi(1)=1=2(1-2^{-1})$. Here equality holds.
Let us thus suppose $k geq 2$. Then $g_k(1)=1-k neq 0$ so $phi(k) neq 1$. Now $phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, frac{2k}{k+1}]$ and decreasing on $[frac{2k}{k+1},infty]$. We have $p(1)=0, p(2)=-1$.
Remark: If we just wanted to prove the weaker statement $lim_{kto infty} phi(k)=2$, note that we clearly have $phi(k) in (frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.
Note $2^k=(1+1)^k geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) geq 2(1-frac{1}{k+1})=frac{2k}{k+1}$. Finally
$$
begin{align}
p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \
&=2(1-2^{-k})^k-1 \
& >2(1-k2^{-k})-1 \
&=1-frac{k}{2^{k-1}} \
& geq 0 \
end{align}$$
where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.
Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,frac{2k}{k+1}]$, $p(x) geq p(2(1-2^{-k}))>0$ on $[frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) leq p(2)<0$ on $[2,infty)$. Thus we conclude $phi(k) in (2(1-2^{-k}), 2)$.
Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $phi(k) in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.
answered Jan 12 at 16:02
user634090user634090
262
$endgroup$
add a comment |
$begingroup$
The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $phi(1)=1=2(1-2^{-1})$. Here equality holds.
Let us thus suppose $k geq 2$. Then $g_k(1)=1-k neq 0$ so $phi(k) neq 1$. Now $phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, frac{2k}{k+1}]$ and decreasing on $[frac{2k}{k+1},infty]$. We have $p(1)=0, p(2)=-1$.
Remark: If we just wanted to prove the weaker statement $lim_{kto infty} phi(k)=2$, note that we clearly have $phi(k) in (frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.
Note $2^k=(1+1)^k geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) geq 2(1-frac{1}{k+1})=frac{2k}{k+1}$. Finally
$$
begin{align}
p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \
&=2(1-2^{-k})^k-1 \
& >2(1-k2^{-k})-1 \
&=1-frac{k}{2^{k-1}} \
& geq 0 \
end{align}$$
where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.
Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,frac{2k}{k+1}]$, $p(x) geq p(2(1-2^{-k}))>0$ on $[frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) leq p(2)<0$ on $[2,infty)$. Thus we conclude $phi(k) in (2(1-2^{-k}), 2)$.
Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $phi(k) in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.
answered Jan 12 at 16:02
user634090user634090
262
$endgroup$
add a comment |
$begingroup$
The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $phi(1)=1=2(1-2^{-1})$. Here equality holds.
Let us thus suppose $k geq 2$. Then $g_k(1)=1-k neq 0$ so $phi(k) neq 1$. Now $phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, frac{2k}{k+1}]$ and decreasing on $[frac{2k}{k+1},infty]$. We have $p(1)=0, p(2)=-1$.
Remark: If we just wanted to prove the weaker statement $lim_{kto infty} phi(k)=2$, note that we clearly have $phi(k) in (frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.
Note $2^k=(1+1)^k geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) geq 2(1-frac{1}{k+1})=frac{2k}{k+1}$. Finally
$$
begin{align}
p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \
&=2(1-2^{-k})^k-1 \
& >2(1-k2^{-k})-1 \
&=1-frac{k}{2^{k-1}} \
& geq 0 \
end{align}$$
where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.
Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,frac{2k}{k+1}]$, $p(x) geq p(2(1-2^{-k}))>0$ on $[frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) leq p(2)<0$ on $[2,infty)$. Thus we conclude $phi(k) in (2(1-2^{-k}), 2)$.
Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $phi(k) in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.
answered Jan 12 at 16:02
user634090user634090
262
$endgroup$
The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $phi(1)=1=2(1-2^{-1})$. Here equality holds.
Let us thus suppose $k geq 2$. Then $g_k(1)=1-k neq 0$ so $phi(k) neq 1$. Now $phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, frac{2k}{k+1}]$ and decreasing on $[frac{2k}{k+1},infty]$. We have $p(1)=0, p(2)=-1$.
Remark: If we just wanted to prove the weaker statement $lim_{kto infty} phi(k)=2$, note that we clearly have $phi(k) in (frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.
Note $2^k=(1+1)^k geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) geq 2(1-frac{1}{k+1})=frac{2k}{k+1}$. Finally
$$
begin{align}
p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \
&=2(1-2^{-k})^k-1 \
& >2(1-k2^{-k})-1 \
&=1-frac{k}{2^{k-1}} \
& geq 0 \
end{align}$$
where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.
Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,frac{2k}{k+1}]$, $p(x) geq p(2(1-2^{-k}))>0$ on $[frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) leq p(2)<0$ on $[2,infty)$. Thus we conclude $phi(k) in (2(1-2^{-k}), 2)$.
Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $phi(k) in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.
answered Jan 12 at 16:02
user634090user634090
262
edited Jan 12 at 16:22
answered Jan 12 at 16:02
user634090user634090
262
answered Jan 12 at 16:02
user634090user634090
262
answered Jan 12 at 16:02
user634090user634090
262
262
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3070958%2fhow-to-show-this-inequality-involving-generalized-fibonacci-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
