0
votes
2answers
43 views

Closed form for recurrence relation

Is there a closed-form solution to the following recurrence: $$T(n) = T(n-1) + T(n-3)$$ If yes, what is it and how can it be proven/derived? If not, then why because a somewhat similar recurrence ...
5
votes
1answer
70 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
0
votes
0answers
13 views

Compact closed form for linear recurrence formulas

Assume you have some linear recursion formula $$f(\vec x)=\sum_{\vec y\in Y}w_{\vec y}f(\vec x - \vec y)$$ Where $\vec y\geq 0 $ and $||\vec y||>0$, $w_{\vec y}\in\mathbb{R}$ and $\vec x , \vec ...
0
votes
1answer
24 views

Going from recurrence relations to closed form

How do I go from the following recurrence relation a(n) = (n+1)a(n-1) where a(0) = 2 to a closed form? I know I need to use an iterative approach but I am not ...
1
vote
2answers
53 views

Closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$

How in God's name could I find a closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$? I'm looking at the first numbers in sequence and I just don't see any relation...
0
votes
2answers
98 views

Does this series $2 + 4 + \cdots + \sqrt{\sqrt{n}} + \sqrt{n} + n$ have a general term?

Does this sum simplify to a general term in terms of $n$? If so, how would you arrive at that term? $2 + 4 + \cdots + \sqrt{\sqrt{n}} + \sqrt{n} + n$. Thanks.
0
votes
1answer
58 views

Can every recurrence relation be solved?

Motivation A possible way to solve an ODE is to express the solution as: $y= \sum_{n=0}^\infty a_nx^n$. We substitute in the ODE and then calculate the coefficients $a_n$. For example, $y''+y=0$ ...
0
votes
0answers
27 views

Closed expression for simple recursive formula

I would like to express the following recursive formula in a closed expression. $V_\tau=(1+R)V_{\tau-1}+\tau(c-p\lambda\mu)+constant$ where: $\tau\geq1$ $V_1=\frac{1}{2}(2u+c-p\lambda\mu)R$ ...
3
votes
2answers
60 views

Does $E^2 \; ( E \approx 1.2640847\ldots)$ equal $D \approx 1.5979102\ldots$?

Does $E^2=D$? Where $E$ is a constant used in the closed form of the Sylvester Sequence (see: Closed form formula and asymptotics) and $D$ is a constant for the closed formula of the sequence A007018 ...
1
vote
1answer
57 views

How to find algebraic simplification for recurrence relation with closed-form solution, specifically for the Lucas-Lehmer primality test

I have a question based on the section Proof of correctness in the article Lucas-Lehmer primality test, see following link. ...
1
vote
1answer
66 views

Is it possible to get a 'closed form' for $\sum_{k=0}^{n} a_k b_{n-k}$?

This came up when trying to divide series, or rather, express $\frac1{f(x)}$ as a series, knowing that $f(x)$ has a zero of order one at $x=0$, and knowing the Taylor series for $f(x)$ (that is ...
1
vote
4answers
109 views

How to solve a recursive equation

I have been given a task to solve the following recursive equation \begin{align*} a_1&=-2\\ a_2&= 12\\ a_n&= -4a_n{}_-{}_1-4a_n{}_-{}_2, \quad n \geq 3. \end{align*} Should I start by ...
2
votes
4answers
581 views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
1
vote
1answer
105 views

Recursive and closed form solution for choosing $n$ pairs/triplets.. of $kn$ elements.

I stumbled apon an interesting question: How many ways are there to arrenge $kn$ elements into $n$ sets, $k$ elements each? There should be a recursive and closed form solution for $g_k(n)$. For ...
0
votes
1answer
105 views

Getting the closed form solution of a third order recurrence relation with constant coefficients

This is part of the proof of finding the closed from solution of third order recurrence relation I know that the closed form will look like the following And this is the part of the proof I can ...
0
votes
2answers
460 views

Finding the closed form solution of a third order recurrence relation with constant coefficients [duplicate]

How would you solve for the closed form solution of a(n) given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
5
votes
3answers
303 views

Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula: $$ a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n $$ This formula is a closed-form expression of a linear ...
3
votes
2answers
429 views

Solving for the closed term solution of a third order recurrence relation with real constant coefficients

How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
2
votes
1answer
250 views

Recurrence relation for $n$ numbers in which no 3 consecutive digits are the same.

I am stuck on trying to find (and solve) a recurrence relation to find all n-digit numbers in which no 3 consecutive digits are the same. These numbers are in decimal expansion. Now I first ...
6
votes
3answers
226 views

Alternating Recurrence relation $a_n = b_{n-1} + 5$ and $b_n = na_{n-1}$

I am racking my brain on solving the relation where: $$a_n = b_{n-1} + 5$$ $$b_n = na_{n-1}$$ where $a_0$ = $b_0$ = 1 I am trying to find the closed form for $a_n$. I have tried to shifting $b_n = ...
20
votes
2answers
401 views

How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$?

I need to calculate the sum $\displaystyle S=\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$, where $\displaystyle H_n=\sum\limits_{m=1}^n\frac1m$. Using a CAS I found that $S=\lim\limits_{k\to\infty}s_k$ ...
3
votes
4answers
109 views

Closed form of a recurrence relation using generating functions

It's been awhile since I have done this. The sequence is $\displaystyle a_n = a_{n-1} + 5~a_{n-2}$ with $a_{0}=0$ and $a_{1}=1$. I found the generating function to be $\displaystyle G(x) = ...
0
votes
1answer
101 views

How to express this recurrence relation as a closed form?

I need a little help with expressing this recurrence relation as a closed form. I've already expanded it out to see the pattern: $$ f(n) = f\left(\frac{n}{3}\right) + f\left(\frac{2n}{3}\right) + n - ...
3
votes
1answer
245 views

Finding a Linear Recurrence Relation

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. ...
2
votes
2answers
77 views

Finding the expression for $q_n$

Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that $$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$ and, ...
1
vote
2answers
57 views

Stuck on solving recurrence relation

I'm trying to find formula for the following sequence. 1, 3, 6, 10, 15... Recursive formula is pretty straightforward My attempt to solve it: Homogeneous solution Particular solution ...
2
votes
1answer
52 views

Recurrence equation question

My question (which has been edited) relates to the following recurrence relation: $$a_{j+2}=\frac{2 a_{j}}{j}$$ The book which I am reading says that the (approximate) solution is given by: ...
-2
votes
1answer
549 views

Find a closed form for a generating function and recurrence

Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$ for $n \geq 2$ and initial conditions $r_0 = ...
2
votes
3answers
103 views

Please help solve the following recurrences

Please help with solving the recurrences to get closed form formulas for $a_n$, $b_n$ and $c_n$. Be sure to clearly label the characteristic equation, the roots of the characteristic equation, the ...
0
votes
4answers
360 views

Having a lot of trouble solving this recurrence with iteration and finding a closed form…

I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, ...
4
votes
5answers
291 views

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
3
votes
0answers
101 views

How to resolve this equation for f(n) without using f(n-1)

I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
0
votes
1answer
92 views

What is the closed form for the general recurrence relation?

$T(N) = a\cdot T(N-b) + c \cdot N + d $ $T(0) = 0$ I honestly don't understand this concept at all. Any help would be great.
1
vote
1answer
95 views

Closed form or upper bound for recursively defined sequence

Is there a closed form of the following sequence: $$u_0 = 2$$ $$u_{n+1} = s_n^2-s_n, \;s_n = \sum_{k=0}^{n} u_k$$ If not, I would like to have an upper bound. By looking at the numbers I guessed ...
1
vote
0answers
104 views

Cycle of remainders

Let $N, K, W$ be natural numbers If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$ and proceed with: $$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$ (that is the remainder of the ...
1
vote
4answers
85 views

Solving a simple recurrence.

This isn't a homework question, but it is a problem in my textbook. Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$ My approach: Given $T(n) = T(n-1)$ Need to show $T(n) = cn^2$, where $c ...
1
vote
0answers
177 views

Closed form expression for a recurrence relation.

Hello, any ideas for computing closed form for a recurrence relation? In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
4
votes
4answers
1k views

Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below. $$F(n) = 2F(n-1) + 2F(n-2)$$ $$F(1) = 1$$ $$F(2) = 3$$ Is there any way it can be easily deduced if the closed form ...
1
vote
1answer
156 views

Simple recurrence relation in three dimensions

I have the following recurrence relation: $$f[i,j,k] = f[i-1,j,k] + f[i,j-1,k] + f[i,j,k-1],\quad \mbox{for } i \geq j+k,$$ starting with $f[0,0,0]=1$, for $i$, $j$, and $k$ non-negative. Is there ...
2
votes
3answers
172 views

Find a closed term for $f(n) = n + 2 f(n-1)$, $f(1)=1$

I cannot help myself, but I don't get the closed term for: $f(n) = n + 2 f(n-1)$, where f(1) = 1. I tried to find the pattern when looking at some iterations, and I think I see the pattern very ...
0
votes
1answer
800 views

Rearranging a general closed form linear recurrence sequence

I have the following general closed form linear recurrence equation: $$x_n=r^{n-1}a+\left(\frac{r^{n-1}-1}{r-1}\right)d, \qquad (n=1,2,3,...)$$ and the next stage in the text shows the equation ...
6
votes
4answers
139 views

closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?

I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular ...
17
votes
5answers
939 views

Find a closed form for this sequence: $a_{n+1} = a_n + a_n^{-1}$

Today, we had a math class, where we had to show, that $a_{100} > 14$ for $$a_0 = 1;\qquad a_{n+1} = a_n + a_n^{-1}$$ Apart from this task, I asked my self: Is there a closed form for this ...