Mixing
Solving a floored input linear recurrence relation
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Need help solving:
$$T(n) = T(n-1) + binomn-1lfloorfracn-12rfloor + 1$$
for $n geq 3$ and $T(1) = 1$, $T(2) = 2$
I believe the answer is $T(n) = binomnlfloorfracn2rfloor$, but do not know how to show this algebraically.
combinatorics recurrence-relations
asked Aug 2 at 0:53
Luciano
133
add a comment |Â
up vote
1
down vote
favorite
Need help solving:
$$T(n) = T(n-1) + binomn-1lfloorfracn-12rfloor + 1$$
for $n geq 3$ and $T(1) = 1$, $T(2) = 2$
I believe the answer is $T(n) = binomnlfloorfracn2rfloor$, but do not know how to show this algebraically.
combinatorics recurrence-relations
asked Aug 2 at 0:53
Luciano
133
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Need help solving:
$$T(n) = T(n-1) + binomn-1lfloorfracn-12rfloor + 1$$
for $n geq 3$ and $T(1) = 1$, $T(2) = 2$
I believe the answer is $T(n) = binomnlfloorfracn2rfloor$, but do not know how to show this algebraically.
combinatorics recurrence-relations
asked Aug 2 at 0:53
Luciano
133
Need help solving:
$$T(n) = T(n-1) + binomn-1lfloorfracn-12rfloor + 1$$
for $n geq 3$ and $T(1) = 1$, $T(2) = 2$
I believe the answer is $T(n) = binomnlfloorfracn2rfloor$, but do not know how to show this algebraically.
combinatorics recurrence-relations
asked Aug 2 at 0:53
Luciano
133
asked Aug 2 at 0:53
Luciano
133
asked Aug 2 at 0:53
Luciano
133
asked Aug 2 at 0:53
Luciano
133
133
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37
add a comment |Â
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
We unroll the recursion to get
$$T(n) = 1+ sum_k=0^n-1 kchoose lfloor k/2rfloor + 1.$$
Induction is the method of choice here. The claim $T(n) = nchoose
lfloor n/2rfloor$ holds for $n=1$ by inspection. Supposing it holds
for $n-1$ we get for $T(n):$
$$n-1choose lfloor (n-1)/2rfloor
+ n-1choose lfloor (n-1)/2rfloor + 1
= n choose lfloor (n-1)/2rfloor + 1.$$
Now when $n=2q$ this is
$$2qchoose q-1+1 = 2qchoose q =
nchoose lfloor n/2 rfloor.$$
On the other hand when $n=2q+1$ it becomes
$$2q+1choose q+1 = 2q+1choose q =
nchoose lfloor n/2 rfloor.$$
This concludes the proof by induction. We present an additional proof
using formal power series, by way of enrichment.
Starting from the closed form we have
$$1 + sum_k=0^lfloor (n-1)/2rfloor 2kchoose k + 1
+ sum_k=0^lfloor n/2rfloor-1 2k+1choose k + 1.$$
Evaluating the first sum we obtain
$$sum_k=0^m 2kchoose k + 1 = sum_k=1^m 2kchoose k - 1
= sum_k=0^m-1 2m -2k choose m-k - 1
= sum_k=0^m-1 [z^m-1-k] (1+z)^2m-2k
\ = [z^m-1] (1+z)^2m sum_k=0^m-1 z^k (1+z)^-2k
= [z^m-1] (1+z)^2m sum_kge 0 z^k (1+z)^-2k
\ = [z^m-1] (1+z)^2m frac11-z/(1+z)^2
\ = [z^m-1] (1+z)^2m+2 frac11+z+z^2.$$
By a very similar calculation we find
$$sum_k=0^m 2k+1choose k + 1
= sum_k=0^m 2m -2k +1 choose m-k + 1
= sum_k=0^m [z^m+1-k] (1+z)^2m-2k+1
\ = [z^m+1] (1+z)^2m+1 sum_k=0^m z^k (1+z)^-2k
= -1 + [z^m+1] (1+z)^2m+1 sum_k=0^m+1 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 sum_kge 0 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 frac11-z/(1+z)^2
\ = -1 + [z^m+1] (1+z)^2m+3 frac11+z+z^2.$$
Collecting the three pieces from the closed form of $T(n)$ we have
cancelation of the minus one term. There are two cases. When $n=2q$ we
get for the upper limits $q-1$ and $q-1$ for a contribution of
$$[z^q-2] (1+z)^2q frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q fracz^21+z+z^2
+ [z^q] (1+z)^2q frac1+z1+z+z^2
\ = [z^q] (1+z)^2q = 2qchoose q.$$
This is the desired value. When $n=2q+1$ the upper limits become $q$ and
$q-1$ and we obtain
$$[z^q-1] (1+z)^2q+2 frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 fracz+z^21+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 = 2q+1choose q.$$
We have shown the closed form
$$bbox[5px,border:2px solid #00A000]
nchoose lfloor n/2 rfloor.$$
This may illustrate certain aspects of the formal power series
technique.
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
We unroll the recursion to get
$$T(n) = 1+ sum_k=0^n-1 kchoose lfloor k/2rfloor + 1.$$
Induction is the method of choice here. The claim $T(n) = nchoose
lfloor n/2rfloor$ holds for $n=1$ by inspection. Supposing it holds
for $n-1$ we get for $T(n):$
$$n-1choose lfloor (n-1)/2rfloor
+ n-1choose lfloor (n-1)/2rfloor + 1
= n choose lfloor (n-1)/2rfloor + 1.$$
Now when $n=2q$ this is
$$2qchoose q-1+1 = 2qchoose q =
nchoose lfloor n/2 rfloor.$$
On the other hand when $n=2q+1$ it becomes
$$2q+1choose q+1 = 2q+1choose q =
nchoose lfloor n/2 rfloor.$$
This concludes the proof by induction. We present an additional proof
using formal power series, by way of enrichment.
Starting from the closed form we have
$$1 + sum_k=0^lfloor (n-1)/2rfloor 2kchoose k + 1
+ sum_k=0^lfloor n/2rfloor-1 2k+1choose k + 1.$$
Evaluating the first sum we obtain
$$sum_k=0^m 2kchoose k + 1 = sum_k=1^m 2kchoose k - 1
= sum_k=0^m-1 2m -2k choose m-k - 1
= sum_k=0^m-1 [z^m-1-k] (1+z)^2m-2k
\ = [z^m-1] (1+z)^2m sum_k=0^m-1 z^k (1+z)^-2k
= [z^m-1] (1+z)^2m sum_kge 0 z^k (1+z)^-2k
\ = [z^m-1] (1+z)^2m frac11-z/(1+z)^2
\ = [z^m-1] (1+z)^2m+2 frac11+z+z^2.$$
By a very similar calculation we find
$$sum_k=0^m 2k+1choose k + 1
= sum_k=0^m 2m -2k +1 choose m-k + 1
= sum_k=0^m [z^m+1-k] (1+z)^2m-2k+1
\ = [z^m+1] (1+z)^2m+1 sum_k=0^m z^k (1+z)^-2k
= -1 + [z^m+1] (1+z)^2m+1 sum_k=0^m+1 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 sum_kge 0 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 frac11-z/(1+z)^2
\ = -1 + [z^m+1] (1+z)^2m+3 frac11+z+z^2.$$
Collecting the three pieces from the closed form of $T(n)$ we have
cancelation of the minus one term. There are two cases. When $n=2q$ we
get for the upper limits $q-1$ and $q-1$ for a contribution of
$$[z^q-2] (1+z)^2q frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q fracz^21+z+z^2
+ [z^q] (1+z)^2q frac1+z1+z+z^2
\ = [z^q] (1+z)^2q = 2qchoose q.$$
This is the desired value. When $n=2q+1$ the upper limits become $q$ and
$q-1$ and we obtain
$$[z^q-1] (1+z)^2q+2 frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 fracz+z^21+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 = 2q+1choose q.$$
We have shown the closed form
$$bbox[5px,border:2px solid #00A000]
nchoose lfloor n/2 rfloor.$$
This may illustrate certain aspects of the formal power series
technique.
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
add a comment |Â
up vote
1
down vote
accepted
We unroll the recursion to get
$$T(n) = 1+ sum_k=0^n-1 kchoose lfloor k/2rfloor + 1.$$
Induction is the method of choice here. The claim $T(n) = nchoose
lfloor n/2rfloor$ holds for $n=1$ by inspection. Supposing it holds
for $n-1$ we get for $T(n):$
$$n-1choose lfloor (n-1)/2rfloor
+ n-1choose lfloor (n-1)/2rfloor + 1
= n choose lfloor (n-1)/2rfloor + 1.$$
Now when $n=2q$ this is
$$2qchoose q-1+1 = 2qchoose q =
nchoose lfloor n/2 rfloor.$$
On the other hand when $n=2q+1$ it becomes
$$2q+1choose q+1 = 2q+1choose q =
nchoose lfloor n/2 rfloor.$$
This concludes the proof by induction. We present an additional proof
using formal power series, by way of enrichment.
Starting from the closed form we have
$$1 + sum_k=0^lfloor (n-1)/2rfloor 2kchoose k + 1
+ sum_k=0^lfloor n/2rfloor-1 2k+1choose k + 1.$$
Evaluating the first sum we obtain
$$sum_k=0^m 2kchoose k + 1 = sum_k=1^m 2kchoose k - 1
= sum_k=0^m-1 2m -2k choose m-k - 1
= sum_k=0^m-1 [z^m-1-k] (1+z)^2m-2k
\ = [z^m-1] (1+z)^2m sum_k=0^m-1 z^k (1+z)^-2k
= [z^m-1] (1+z)^2m sum_kge 0 z^k (1+z)^-2k
\ = [z^m-1] (1+z)^2m frac11-z/(1+z)^2
\ = [z^m-1] (1+z)^2m+2 frac11+z+z^2.$$
By a very similar calculation we find
$$sum_k=0^m 2k+1choose k + 1
= sum_k=0^m 2m -2k +1 choose m-k + 1
= sum_k=0^m [z^m+1-k] (1+z)^2m-2k+1
\ = [z^m+1] (1+z)^2m+1 sum_k=0^m z^k (1+z)^-2k
= -1 + [z^m+1] (1+z)^2m+1 sum_k=0^m+1 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 sum_kge 0 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 frac11-z/(1+z)^2
\ = -1 + [z^m+1] (1+z)^2m+3 frac11+z+z^2.$$
Collecting the three pieces from the closed form of $T(n)$ we have
cancelation of the minus one term. There are two cases. When $n=2q$ we
get for the upper limits $q-1$ and $q-1$ for a contribution of
$$[z^q-2] (1+z)^2q frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q fracz^21+z+z^2
+ [z^q] (1+z)^2q frac1+z1+z+z^2
\ = [z^q] (1+z)^2q = 2qchoose q.$$
This is the desired value. When $n=2q+1$ the upper limits become $q$ and
$q-1$ and we obtain
$$[z^q-1] (1+z)^2q+2 frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 fracz+z^21+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 = 2q+1choose q.$$
We have shown the closed form
$$bbox[5px,border:2px solid #00A000]
nchoose lfloor n/2 rfloor.$$
This may illustrate certain aspects of the formal power series
technique.
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
We unroll the recursion to get
$$T(n) = 1+ sum_k=0^n-1 kchoose lfloor k/2rfloor + 1.$$
Induction is the method of choice here. The claim $T(n) = nchoose
lfloor n/2rfloor$ holds for $n=1$ by inspection. Supposing it holds
for $n-1$ we get for $T(n):$
$$n-1choose lfloor (n-1)/2rfloor
+ n-1choose lfloor (n-1)/2rfloor + 1
= n choose lfloor (n-1)/2rfloor + 1.$$
Now when $n=2q$ this is
$$2qchoose q-1+1 = 2qchoose q =
nchoose lfloor n/2 rfloor.$$
On the other hand when $n=2q+1$ it becomes
$$2q+1choose q+1 = 2q+1choose q =
nchoose lfloor n/2 rfloor.$$
This concludes the proof by induction. We present an additional proof
using formal power series, by way of enrichment.
Starting from the closed form we have
$$1 + sum_k=0^lfloor (n-1)/2rfloor 2kchoose k + 1
+ sum_k=0^lfloor n/2rfloor-1 2k+1choose k + 1.$$
Evaluating the first sum we obtain
$$sum_k=0^m 2kchoose k + 1 = sum_k=1^m 2kchoose k - 1
= sum_k=0^m-1 2m -2k choose m-k - 1
= sum_k=0^m-1 [z^m-1-k] (1+z)^2m-2k
\ = [z^m-1] (1+z)^2m sum_k=0^m-1 z^k (1+z)^-2k
= [z^m-1] (1+z)^2m sum_kge 0 z^k (1+z)^-2k
\ = [z^m-1] (1+z)^2m frac11-z/(1+z)^2
\ = [z^m-1] (1+z)^2m+2 frac11+z+z^2.$$
By a very similar calculation we find
$$sum_k=0^m 2k+1choose k + 1
= sum_k=0^m 2m -2k +1 choose m-k + 1
= sum_k=0^m [z^m+1-k] (1+z)^2m-2k+1
\ = [z^m+1] (1+z)^2m+1 sum_k=0^m z^k (1+z)^-2k
= -1 + [z^m+1] (1+z)^2m+1 sum_k=0^m+1 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 sum_kge 0 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 frac11-z/(1+z)^2
\ = -1 + [z^m+1] (1+z)^2m+3 frac11+z+z^2.$$
Collecting the three pieces from the closed form of $T(n)$ we have
cancelation of the minus one term. There are two cases. When $n=2q$ we
get for the upper limits $q-1$ and $q-1$ for a contribution of
$$[z^q-2] (1+z)^2q frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q fracz^21+z+z^2
+ [z^q] (1+z)^2q frac1+z1+z+z^2
\ = [z^q] (1+z)^2q = 2qchoose q.$$
This is the desired value. When $n=2q+1$ the upper limits become $q$ and
$q-1$ and we obtain
$$[z^q-1] (1+z)^2q+2 frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 fracz+z^21+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 = 2q+1choose q.$$
We have shown the closed form
$$bbox[5px,border:2px solid #00A000]
nchoose lfloor n/2 rfloor.$$
This may illustrate certain aspects of the formal power series
technique.
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
We unroll the recursion to get
$$T(n) = 1+ sum_k=0^n-1 kchoose lfloor k/2rfloor + 1.$$
Induction is the method of choice here. The claim $T(n) = nchoose
lfloor n/2rfloor$ holds for $n=1$ by inspection. Supposing it holds
for $n-1$ we get for $T(n):$
$$n-1choose lfloor (n-1)/2rfloor
+ n-1choose lfloor (n-1)/2rfloor + 1
= n choose lfloor (n-1)/2rfloor + 1.$$
Now when $n=2q$ this is
$$2qchoose q-1+1 = 2qchoose q =
nchoose lfloor n/2 rfloor.$$
On the other hand when $n=2q+1$ it becomes
$$2q+1choose q+1 = 2q+1choose q =
nchoose lfloor n/2 rfloor.$$
This concludes the proof by induction. We present an additional proof
using formal power series, by way of enrichment.
Starting from the closed form we have
$$1 + sum_k=0^lfloor (n-1)/2rfloor 2kchoose k + 1
+ sum_k=0^lfloor n/2rfloor-1 2k+1choose k + 1.$$
Evaluating the first sum we obtain
$$sum_k=0^m 2kchoose k + 1 = sum_k=1^m 2kchoose k - 1
= sum_k=0^m-1 2m -2k choose m-k - 1
= sum_k=0^m-1 [z^m-1-k] (1+z)^2m-2k
\ = [z^m-1] (1+z)^2m sum_k=0^m-1 z^k (1+z)^-2k
= [z^m-1] (1+z)^2m sum_kge 0 z^k (1+z)^-2k
\ = [z^m-1] (1+z)^2m frac11-z/(1+z)^2
\ = [z^m-1] (1+z)^2m+2 frac11+z+z^2.$$
By a very similar calculation we find
$$sum_k=0^m 2k+1choose k + 1
= sum_k=0^m 2m -2k +1 choose m-k + 1
= sum_k=0^m [z^m+1-k] (1+z)^2m-2k+1
\ = [z^m+1] (1+z)^2m+1 sum_k=0^m z^k (1+z)^-2k
= -1 + [z^m+1] (1+z)^2m+1 sum_k=0^m+1 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 sum_kge 0 z^k (1+z)^-2k
\ = -1 + [z^m+1] (1+z)^2m+1 frac11-z/(1+z)^2
\ = -1 + [z^m+1] (1+z)^2m+3 frac11+z+z^2.$$
Collecting the three pieces from the closed form of $T(n)$ we have
cancelation of the minus one term. There are two cases. When $n=2q$ we
get for the upper limits $q-1$ and $q-1$ for a contribution of
$$[z^q-2] (1+z)^2q frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q fracz^21+z+z^2
+ [z^q] (1+z)^2q frac1+z1+z+z^2
\ = [z^q] (1+z)^2q = 2qchoose q.$$
This is the desired value. When $n=2q+1$ the upper limits become $q$ and
$q-1$ and we obtain
$$[z^q-1] (1+z)^2q+2 frac11+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 fracz+z^21+z+z^2
+ [z^q] (1+z)^2q+1 frac11+z+z^2
\ = [z^q] (1+z)^2q+1 = 2q+1choose q.$$
We have shown the closed form
$$bbox[5px,border:2px solid #00A000]
nchoose lfloor n/2 rfloor.$$
This may illustrate certain aspects of the formal power series
technique.
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
edited Aug 3 at 19:18
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
answered Aug 3 at 18:21
Marko Riedel
36.4k333106
36.4k333106
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
add a comment |Â
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
Good point in using complex analysis tools here!
– Vim
Aug 3 at 18:24
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
wow that's really like black magic! I never heard of formal residue operator before.
– Vim
Aug 3 at 18:39
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
thanks for the ref. And apologies for I should have perhaps used "black tech" instead of "black magic" which I mistakenly used in my comment (not a native speaker).
– Vim
Aug 3 at 18:47
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
Edited to use formal power series only, no reference to complex variables.
– Marko Riedel
Aug 3 at 19:07
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%2f2869630%2fsolving-a-floored-input-linear-recurrence-relation%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
Recall that $$binom n k = binomn-1k-1+binomn-1k. $$
– Math1000
Aug 2 at 1:42
Just assume your guess is correct and prove it by induction.
– saulspatz
Aug 2 at 3:35
Not an answer, but $T(2)$ doesn't need to be a special case: $T(1) + binom11 = 2$.
– Peter Taylor
Aug 2 at 7:37