21
votes
Solve recurrence relation
This type of equations can be solved in terms of "factorial series", as explained in the book:
N. E. Nørlund, Leçons sur les équations linéaires aux differences finies, Paris, Gauthier-...
- 91.8k
11
votes
Accepted
Combinatorial identity with connection coefficients and falling factorial $\langle i x\rangle_n$
It is very probable that what is written below is the simplification of Darij's argument. I use the notation $x^{\underline{n}}=x(x-1)\dots(x-n+1)$ [as in Knuth's books] for the falling factorial, and ...
- 109k
11
votes
Accepted
Solve recurrence relation
The publication Closed-form solutions of general second order linear recurrences and applications may be helpful. It gives two forms of solution for
$$f(n)=b_{n-1}f(n-1)+a_{n-2}f(n-2).$$
One solution ...
- 188k
10
votes
Accepted
Double q-analog of Pochhammer
This product appears in permutation enumeration. See, for example, D. P. Roselle, Coefficients associated with the expansion of certain products (DOI), Proc. Amer. Math. Soc. 45 (1974), 144-150.
- 17k
9
votes
Combinatorial identity with connection coefficients and falling factorial $\langle i x\rangle_n$
This is correct. Let me prove a more general fact:
Theorem 1. Let $i$, $j$ and $n$ be three nonnegative integers such that
$i\leq n$ and $j\leq n$. Let $P\in\mathbb{Q}\left[ X\right] $ be a
...
- 33.8k
8
votes
Accepted
Does this deceptively simple nonlinear recurrence relation have a closed form solution?
The sequence $a_n$ for $n\geq 1$ has the following formula:
$$a_n=\left\lfloor \sqrt{2n}+\tfrac{1}{2}\right\rfloor +\frac{\left\lfloor \frac{1}{2} \left(\sqrt{8 n-7}+1\right)\right\rfloor-\left\lfloor ...
- 188k
6
votes
Accepted
A strange two-variable recursion
First, we note that $f(m,n) - f(m,n-1)$ does not depend on $n$, so for a fixed $m$ we can write $f(m,n) = \alpha_m n + \beta_m$ for some $\alpha_m,\beta_m$ which depend only on $m$. Imposing the ...
- 1,247
6
votes
Solve recurrence relation
Here is a derivation of the generating function as a solution of an ODE of the first order with Maple 2024 (see here for info).
...
- 3,486
6
votes
Accepted
Solving a specific difference equation
In the limit $d\to\infty$ the op's difference equation can be transformed into an ordinary differential equation, which can be solved exactly.
We define $\tau=t/d$ and expand
$\beta(\tau) = \beta_{\...
- 3,671
5
votes
Accepted
Change of variable formulas in discrete calculus?
In terms of the differential operator $\partial_x\equiv d/dx$ one has $f(x+h)=e^{h\partial_x}f(x)$, hence
$$\Delta_h=e^{h\partial_x}-1.$$
Upon Fourier transformation, $\hat{f}(k)=\int_{-\infty}^\infty ...
- 188k
5
votes
Great literature on discrete dynamical systems and/or qualitative theory of difference equations
I feel like I already gave this advice, but I want to recommend P. Kurka's Topological and Symbolic Dynamics (2003). The first $\approx$ 100 of pages are a really great general introduction to ...
4
votes
What is the inverse of a triangular matrix whose nonzero elements are binomial coefficients? What is the closed-form solution to a recursive relation?
Using the answer of @Toni, the sequence $u_k$ can be related to the Bernoulli numbers $B_k$ for $k\geq 0$,
\begin{align}\tag{1}
u_{k+1}= \frac{B_{k}}{k!}.
\end{align}
After some algebra, the inverse ...
- 3,671
4
votes
Accepted
What is the inverse of a triangular matrix whose nonzero elements are binomial coefficients? What is the closed-form solution to a recursive relation?
This may answer the question, the sequence is the only implicit thing. I consider $Q=\begin{pmatrix}Q_{i,j}\end{pmatrix}_{n\times n}$ for $n\ge 3$, where
$$Q_{i,j}=
\begin{cases}
\dbinom{j}{i-1}, &...
- 785
4
votes
Accepted
Asymptotic behavior of a recursion
Consider the generating function:
$$F(z,t) := \sum_{n\geq 1}\sum_{N\geq0} x_n(N) z^{n-1} t^N.$$
Then $F(z,0)=\frac1{1-z}$ and
$$\frac\partial{\partial t} F(z,t) = F(z,t)^2 + 10F(z,t).$$
Solving this ...
- 34.3k
3
votes
Polynomial solutions to a difference equation
A few minor comments which don't fit conveniently into the comment fields (and would resist to future edits):
Assuming that a monic solution $P$ has degree $m$, then comparing coefficients at $x^{m+1}...
- 22.5k
3
votes
Difference equation and formal series
In general, this question makes sense at a formal level near $\infty$ only, i.e. for power series involving negative powers of $x$. Setting $z:=\frac{1}{x}$, the equation becomes a so-called ...
- 5,428
3
votes
Difference equation and formal series
The equation $f(x+1)-f(x)=g(x)$ can be viewed as a "discrete derivative", hence a solution $f(x)$ can not be expected to be unique.
\begin{align} f(x+1)-f(x)&=\sum_{j\geq0}f_j\sum_{k=0}^j\binom{j}...
- 43.2k
3
votes
Does this deceptively simple nonlinear recurrence relation have a closed form solution?
I have decided to call this sequence $\Theta_n$ for the triangular-harmonic number sequence because it clearly has properties related to both triangular and harmonic numbers.
I had been studying it ...
- 387
3
votes
Does this deceptively simple nonlinear recurrence relation have a closed form solution?
A similar, possibly simpler closed form is the following: set $$b_n=\left\lfloor\frac{1+\sqrt{8n-7}}{2}\right\rfloor,$$
then $$a_n=\frac{b_n+1}{2}+\frac{n-1}{b_n}.$$
It is not hard to derive this from ...
- 393
3
votes
Accepted
A problem from linear algebra and difference equations
I'm going to use the notation defined above here. When a letter is used alone, it denotes the entire sequence.
Claim: If $C^{[j]}(f, g) = 0$ for all $j \leq k$, then $g^{[k]}$ is a linear ...
- 4,991
3
votes
Accepted
Finite realization of irrational transfer functions
There is at least one (rather trivial) way to formalize "implementability" that has the property that the only implementable functions are rational. Suppose that the implementation is defined as a ...
- 61.9k
2
votes
Laplace's summation formula
One can find a good collection of summation formulae in Interpolation by J. F. Steffensen (1950).
§12. Laplace’s and Gauss’s Summation-Formulas
§14. Euler’s Summation-Formula
§15. Lubbock’s and ...
- 12.3k
2
votes
Accepted
How to solve this conditional recurrence relation?(two variable and conditions)
Under the assumption that $F(2i,n) = 0$ when $i<4$ or $2i>n$, the first and second cases in the recurrence become partial cases of the third one. Hence, the recurrence reduces to
$$F(2i,n) =
\...
- 34.3k
2
votes
Change of variable formulas in discrete calculus?
$\newcommand\De\Delta$Elementarily: The relation $f=\De_h^{-1}g$ means that $f(x+h)-f(x)=g(x)$ for all $x$.
For a function $g$ and each real $r$, we know $f_r:=\De_1^{-1}g_r$, where $g_r(x):=g(rx)$, ...
- 128k
2
votes
Accepted
Solutions of complex linear difference equations
Look for a solution of the form $f(z)=e^{\lambda z}$. Plugging this to your equation, you obtain that
$\lambda$ must be a zero of the entire function
$$F(\lambda)=\sum_{j=1}^n e^{\lambda\eta_j}.$$
...
- 91.8k
2
votes
High order difference operator applied to 1/u
You can apply the formula
$$\Delta^p f(x)=\sum_{k=0}^p{p\choose k}(-1)^{p-k}f(x+k)$$
to $f(x)=1/u(x)$. Further simplification will need knowledge how $u(x)$ depends on $x$.
For example, if $u(x)=x$ ...
- 188k
2
votes
Great literature on discrete dynamical systems and/or qualitative theory of difference equations
For discrete dynamical systems, I think you can hardly do better than the book by Katok and Hasselblatt, Introduction to the Modern Theory of Dynamical Systems.
Unfortunately, I know of no good ...
1
vote
Accepted
Unique zero solution to a difference equation via Laplace transform
Your condition can be rewritten as the system of three equations:
$$au(x)+bu(x+1/2)=0\ \forall x\in(0,1/2), \tag{1}$$
$$au(x)+cu(x-1/2)=0\ \forall x\in(1/2,1), \tag{2} $$
$$au(1/2)=0. \tag{3} $$
In ...
- 128k
1
vote
Accepted
Is this recurrent sequence decreasing?
Since $x_0=0$, it will be convenient to do summation starting from $t=0$.
Denoting $r:=1-p-q$, we have
\begin{split}
S_n &= \frac1n\sum_{t=0}^n \left(pr^{2t} + (q-p)r^{t} - q\right) \\
&=\frac{...
- 34.3k
1
vote
Accepted
On difference identities and $[K:F]$
The answer is yes and appears in R. Cohn's book 'Difference algebra' Lemma II p. 201.
- 1,555
Only top scored, non community-wiki answers of a minimum length are eligible