Mixing
Induction proof of Zeckendorf's theorem for Narayana's sequence
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am stuck doing the proof by induction of the following equation:
$$ 4 M_n = M_n+3 + M_n-1 + M_n-6 + M_n-7 $$
$M_n$ is defined by: $$M_n= M_n-1 + M_n-3$$
I've executed the proof for the base case = $11$. Now I am proceeding to prove it for $n=k+1$, but I'm stuck in the middle. I need to prove that my right side yields $4M_k+1$ just like the left side. Here's what I have done so far:
begineqnarray*
4M_k+1 &=& M_k+4 + M_k + M_k-5 + M_k-6 \
&=& M_k+4 + M_k + M_k-5 + M_k-6 +M_k-7 - M_k-7 \
&=& M_k+4 + M_k + M_k-4 + M_k-6- M_k-7 \
&=& M_k+4 + M_k + M_k-3- M_k-7 \
&=& M_k+4 + M_k-1+ M_k-3 + M_k-3- M_k-7 \
endeqnarray*
I'm at a lost regarding what to be done next. I can't see any ways to subsitute so that I can $4M_k+1$ somehow.
number-theory induction
asked Jul 31 at 14:04
tex_mate
184
add a comment |Â
up vote
1
down vote
favorite
I am stuck doing the proof by induction of the following equation:
$$ 4 M_n = M_n+3 + M_n-1 + M_n-6 + M_n-7 $$
$M_n$ is defined by: $$M_n= M_n-1 + M_n-3$$
I've executed the proof for the base case = $11$. Now I am proceeding to prove it for $n=k+1$, but I'm stuck in the middle. I need to prove that my right side yields $4M_k+1$ just like the left side. Here's what I have done so far:
begineqnarray*
4M_k+1 &=& M_k+4 + M_k + M_k-5 + M_k-6 \
&=& M_k+4 + M_k + M_k-5 + M_k-6 +M_k-7 - M_k-7 \
&=& M_k+4 + M_k + M_k-4 + M_k-6- M_k-7 \
&=& M_k+4 + M_k + M_k-3- M_k-7 \
&=& M_k+4 + M_k-1+ M_k-3 + M_k-3- M_k-7 \
endeqnarray*
I'm at a lost regarding what to be done next. I can't see any ways to subsitute so that I can $4M_k+1$ somehow.
number-theory induction
asked Jul 31 at 14:04
tex_mate
184
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am stuck doing the proof by induction of the following equation:
$$ 4 M_n = M_n+3 + M_n-1 + M_n-6 + M_n-7 $$
$M_n$ is defined by: $$M_n= M_n-1 + M_n-3$$
I've executed the proof for the base case = $11$. Now I am proceeding to prove it for $n=k+1$, but I'm stuck in the middle. I need to prove that my right side yields $4M_k+1$ just like the left side. Here's what I have done so far:
begineqnarray*
4M_k+1 &=& M_k+4 + M_k + M_k-5 + M_k-6 \
&=& M_k+4 + M_k + M_k-5 + M_k-6 +M_k-7 - M_k-7 \
&=& M_k+4 + M_k + M_k-4 + M_k-6- M_k-7 \
&=& M_k+4 + M_k + M_k-3- M_k-7 \
&=& M_k+4 + M_k-1+ M_k-3 + M_k-3- M_k-7 \
endeqnarray*
I'm at a lost regarding what to be done next. I can't see any ways to subsitute so that I can $4M_k+1$ somehow.
number-theory induction
asked Jul 31 at 14:04
tex_mate
184
I am stuck doing the proof by induction of the following equation:
$$ 4 M_n = M_n+3 + M_n-1 + M_n-6 + M_n-7 $$
$M_n$ is defined by: $$M_n= M_n-1 + M_n-3$$
I've executed the proof for the base case = $11$. Now I am proceeding to prove it for $n=k+1$, but I'm stuck in the middle. I need to prove that my right side yields $4M_k+1$ just like the left side. Here's what I have done so far:
begineqnarray*
4M_k+1 &=& M_k+4 + M_k + M_k-5 + M_k-6 \
&=& M_k+4 + M_k + M_k-5 + M_k-6 +M_k-7 - M_k-7 \
&=& M_k+4 + M_k + M_k-4 + M_k-6- M_k-7 \
&=& M_k+4 + M_k + M_k-3- M_k-7 \
&=& M_k+4 + M_k-1+ M_k-3 + M_k-3- M_k-7 \
endeqnarray*
I'm at a lost regarding what to be done next. I can't see any ways to subsitute so that I can $4M_k+1$ somehow.
number-theory induction
asked Jul 31 at 14:04
tex_mate
184
asked Jul 31 at 14:04
tex_mate
184
asked Jul 31 at 14:04
tex_mate
184
asked Jul 31 at 14:04
tex_mate
184
184
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that
$$
M_n+3-4M_n+M_n-1+M_n-6+M_n-7stackrel?=0tag*
$$
holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_i=M_i-1+M_i-3$, and regroup. You get
$$
big(M_n+2-4M_n-1+M_n-2+M_n-7+M_n-8big)+big(M_n-4M_n-3+M_n-4+M_n-9+M_n-10big)
$$
But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_n=M_n-1$:
$$
M_n = M_n-1+M_n-3stackreltextind=M_n-2+M_n-4=M_n-1
$$
Since the equation $M_n=M_n-1$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_n+1$. Your recurrence $M_n+3=M_n+2+M_n$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.tag1$$ On the other hand, the recurrence you want to prove is
$$(L^10-4L^7+L^6+L+1)M=0.tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^10-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that
$$
M_n+3-4M_n+M_n-1+M_n-6+M_n-7stackrel?=0tag*
$$
holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_i=M_i-1+M_i-3$, and regroup. You get
$$
big(M_n+2-4M_n-1+M_n-2+M_n-7+M_n-8big)+big(M_n-4M_n-3+M_n-4+M_n-9+M_n-10big)
$$
But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_n=M_n-1$:
$$
M_n = M_n-1+M_n-3stackreltextind=M_n-2+M_n-4=M_n-1
$$
Since the equation $M_n=M_n-1$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_n+1$. Your recurrence $M_n+3=M_n+2+M_n$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.tag1$$ On the other hand, the recurrence you want to prove is
$$(L^10-4L^7+L^6+L+1)M=0.tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^10-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
add a comment |Â
up vote
0
down vote
accepted
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that
$$
M_n+3-4M_n+M_n-1+M_n-6+M_n-7stackrel?=0tag*
$$
holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_i=M_i-1+M_i-3$, and regroup. You get
$$
big(M_n+2-4M_n-1+M_n-2+M_n-7+M_n-8big)+big(M_n-4M_n-3+M_n-4+M_n-9+M_n-10big)
$$
But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_n=M_n-1$:
$$
M_n = M_n-1+M_n-3stackreltextind=M_n-2+M_n-4=M_n-1
$$
Since the equation $M_n=M_n-1$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_n+1$. Your recurrence $M_n+3=M_n+2+M_n$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.tag1$$ On the other hand, the recurrence you want to prove is
$$(L^10-4L^7+L^6+L+1)M=0.tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^10-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that
$$
M_n+3-4M_n+M_n-1+M_n-6+M_n-7stackrel?=0tag*
$$
holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_i=M_i-1+M_i-3$, and regroup. You get
$$
big(M_n+2-4M_n-1+M_n-2+M_n-7+M_n-8big)+big(M_n-4M_n-3+M_n-4+M_n-9+M_n-10big)
$$
But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_n=M_n-1$:
$$
M_n = M_n-1+M_n-3stackreltextind=M_n-2+M_n-4=M_n-1
$$
Since the equation $M_n=M_n-1$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_n+1$. Your recurrence $M_n+3=M_n+2+M_n$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.tag1$$ On the other hand, the recurrence you want to prove is
$$(L^10-4L^7+L^6+L+1)M=0.tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^10-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that
$$
M_n+3-4M_n+M_n-1+M_n-6+M_n-7stackrel?=0tag*
$$
holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_i=M_i-1+M_i-3$, and regroup. You get
$$
big(M_n+2-4M_n-1+M_n-2+M_n-7+M_n-8big)+big(M_n-4M_n-3+M_n-4+M_n-9+M_n-10big)
$$
But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_n=M_n-1$:
$$
M_n = M_n-1+M_n-3stackreltextind=M_n-2+M_n-4=M_n-1
$$
Since the equation $M_n=M_n-1$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_n+1$. Your recurrence $M_n+3=M_n+2+M_n$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.tag1$$ On the other hand, the recurrence you want to prove is
$$(L^10-4L^7+L^6+L+1)M=0.tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^10-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
edited Jul 31 at 20:13
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
answered Jul 31 at 14:58
Mike Earnest
14.7k11644
14.7k11644
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868067%2finduction-proof-of-zeckendorfs-theorem-for-narayanas-sequence%23new-answer', 'question_page');
);
Post as a guest
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
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
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