1
vote
0answers
13 views

Almost complete multivariate recurrence solution…

$$ \gamma c_{jm_1m_2} = s^+_{jm_1}c_{j(m_1+1)m_2} - s^+_{jm_2}c_{jm_1(m_2+1)}\\ \gamma d_{jm_1m_2} = s^-_{jm_1}d_{j(m_1-1)m_2} - s^-_{jm_2}d_{jm_1(m_2-1)} $$ where $s_{jm_i}^{\pm} = ...
1
vote
2answers
41 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
97 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
48 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
26 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
58 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
51 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
64 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 ...
0
votes
3answers
88 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
427 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
100 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
102 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
414 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
298 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
1answer
321 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
230 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
212 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 = ...
18
votes
2answers
306 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
106 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
92 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
227 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
76 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
54 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
494 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
294 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
283 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
97 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
86 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
96 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
84 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
175 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
154 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
168 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
773 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
138 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
904 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 ...