Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms (2)

0
votes
0answers
12 views

Simple closed functional form for summed recurrence relation

I'm struggling to obtain a simple closed form for a summed recurrence relation. I have an overall form $y=A\left(n-\sum_i^n\frac{e^{-x_i}}{B}\right)$ where $x_{i+1}=kx_i+m$ with $A,B,m >1$ and ...
3
votes
5answers
60 views

How can I solve this recurrence relation: $a_n = 3a_{n-1} + \frac{4^n}{4}$?

How can I solve the following recurrence relation? $$a_n = 3a_{n-1} + \frac{4^n}{4}$$ I know that $a_n^{(h)} = 3a_{n-1}$ and that the characteristic equation is: $$r-3 = 0$$ and thus: $$a_n^{(h)} = ...
0
votes
0answers
38 views

Help fix this proof.

What is wrong with this proof? I followed the example of the answer to another one of my questions, here Define a general recurrence relation as $$f(x)^2=A(x)+B(x)f(x+n).$$ Substitute the root ...
0
votes
1answer
20 views

Closed solution to double recursion

I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, ...
0
votes
2answers
23 views

Recurrence Relation solution

How do I solve the following recurrence relation and what kind is it ? $ a_n = a_{n-1} + c $ ? where c is constant Can this relation be considered non-homogenous as $ F(n) = c.n^0 $ ?
1
vote
1answer
33 views

Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence ...
0
votes
2answers
15 views

$T(n) = 3T(n/3) + c$ using substitution, geometric series

so I have to find the asymptotic complexity of $T(n) = 3Tn(n/3) + c$ using either the substitution method, a recursion tree or induction. I used the Master Theorem to find an answer, but can't use ...
-1
votes
1answer
41 views

Recurrence relation solving [on hold]

The recurrence relation given is $$ T(n) = 2T(\lceil\sqrt{n}\rceil) + 1, \text{ with }T(1) = 1 $$ I want an explanation about the order of the solution of this recurrence relation
0
votes
1answer
19 views

Substitution method for solving recurrences

I see this in CLRS: We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence ...
0
votes
0answers
42 views

Finding the explicit formula of linear homogeneous recurrence relations.

I'm not sure if this equation is a linear homogeneous recurrence relation because I didn't learn math in english. what is the explicit formula for $f$? $f(x) = f(x-2)-{n^{x-1}\over NW-1} ...
4
votes
2answers
60 views

Choose initial values such that sequence always has integer values

We are given a recurrence relation defined by $$x_{n+2}=\frac{x_{n+1}x_n}{2x_n-x_{n+1}}.$$ Place necessary and sufficient values on $x_0$ and $x_1$ such that $x_n$ is an integer for all positive ...
-1
votes
0answers
24 views

Confluent hypergeometric function recurrence relation

How to prove the following contiguous relation for the Kummer function $M(a,b,z)$: $$(a−1+z)M(a,b,z)+(b−a)M(a−1,b,z)+(1−b)M(a,b−1,z)=0.$$
1
vote
3answers
54 views

Ordered Sum of Odd Numbers

EDIT: The vectors can be any length. That is $k$ is not fixed. For a given natural number $n$, let $S_1(n)$ be the number of vectors $(a_1, a_2, \ldots, a_k)$ such that $$a_1 + a_2 + \cdots + a_k = ...
1
vote
1answer
34 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
4
votes
3answers
250 views

Mathematical Induction proof for a cubic equation.

If $ x^3 = x +1$, prove by induction that $ x^{3n} = a_{n}x + b_n + \frac {c_n}{x}$, where $a_1=1, b_1=1, c_1=0$ and $a_n = a_{n-1} + b_{n-1}, b_n = a_{n-1} + b_{n-1} + c_{n-1}, c_n = a_{n-1} + ...
4
votes
1answer
92 views

Infinitely nested radical problem?

I became interested in this nested radical from another question and thought I would have a go at trying to come up with a formula for it. It is $$G(0)=\sqrt{1+\sqrt{2+\sqrt{4+\sqrt{8+\cdots}}}}.$$ ...
0
votes
1answer
25 views

Solve a recurrence in terms of n

I'm trying to determine the order of growth of a recursive algorithm but I only got a recurrence. Please somebody explain me how to solve the following recurrence with $k = 2$: ...
4
votes
2answers
126 views

Convergence of sequence: $f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}$

I am trying to work out a problem on some old analysis qual exam, and managed to reduce it to this question, but I can't seem to figure out this final step: Consider the sequence defined by the ...
3
votes
1answer
33 views

Solving recurrence equation with floor and ceil functions

I have a recurrence equation that would be very easy to solve (without ceil and floor functions) but I can't solve them exactly including floor and ceil. \begin{align} k (1) &= 0\\ k(n) &= ...
1
vote
0answers
24 views

asymptotics of Involutions recurrence relation

Consider the following recurrence relation where $t(n)$ is the number of involutions on $\{1,...,n\}$ \begin{equation} (n+1)t(n)+t(n+1)-t(n+2)=0 \end{equation} When $n \rightarrow \infty$, Wimp and ...
0
votes
1answer
35 views

Linear Recurrence Using matrix exponentiation

Matrix Exponentiation can be used to solve Linear Recurrence . I know how to solve linear recurrences like : $f(n) = f(n-k_1) + f(n-k_2) + ... +\ constant$ But i couldn't find any information on how ...
2
votes
0answers
46 views

Recurrence equation approximation

I have the following recurrence relation, $$x_{i+1}=a\cdot x_i^{\frac{2-2\alpha}{3}}+x_i,$$ where $a>0, \alpha>0$, and $x_0>0$. My goal is to get an approximate the expression for $x_i$. I ...
0
votes
1answer
56 views

Are there ways to separate the Fibonacci sequence? [closed]

I am wondering if there are ways to separate the set of Fibonacci numbers, $F$, into sets $A$ and $B$ such that $$A + B = \{a+b:a\in A,\,b\in B\}=F$$ and such that $A$ and $B$ do not follow the ...
1
vote
2answers
37 views

Closed form for multiplicative recurrence relation

In this StackOverflow question, I found an interesting recurrence relation: $$f(n) = \begin{cases} 1 & n \leq 2 \\ nf(n-1) + (n-1)f(n-2) & \text{otherwise.}\end{cases}$$ I plugged it into ...
0
votes
1answer
64 views

Recurrence relation: $c_{k+1}=c_k+\frac{1}{(k+1)!}$

I have no idea how to proceed solving a recurrence relation like this. I know that the terms approach $e$ but beyond that I have no idea. The relation is$$c_{k+1}=c_k+\frac{1}{(k+1)!} \ \ ; \ c_0=1$$ ...
1
vote
0answers
33 views

Special Non-linear recurrence

Problem I have a non-linear recurrence relation given by $$ a_n = a_{n-1}+a_{n-2}+a_{n-3} - \sqrt{a_{n-1}.a_{n-2}+a_{n-2}.a_{n-3}+a_{n-3}.a_{n-1}} $$ Given $ a_1, a_2 $ and $ a_3 $,I have to find ...
2
votes
1answer
59 views

Find product limit of this recursively-defined sequence?

Problem: if $a_1=3$, $a_n=2a_{n-1}^2-1$, $n\ge2$, find the limit of this expression: $$\lim\limits_{n \to ∞} \prod\limits_{k=1}^{n-1} (1+\frac {1}{a_k})$$ The original problem asks to find ...
4
votes
2answers
206 views

Finding a recurrence for a sum

I am trying to implement the following sum using a programming language: $$\sum_{i=1}^N a^i i^r$$ where $N$, $a$ and $r$ are integers. The problem is, I cannot find a suitable way to do this. ...
1
vote
2answers
39 views

The derivative of a recurrence relation of functions

I am unsure of how to take the derivative of a recurrence relation of functions. For example consider the following recurrence relation: \begin{equation} \left\{ \begin{array}{cl} f_n(x) &= ...
4
votes
1answer
47 views

Recurrence relation in terms of another sequence

How do I solve a recurrence of the form $$nd^{n-1}a_n+a_{n+1}d^{n+1}=b_n$$ for $a_n$, where $b_n$ is another (known) sequence and $d$ is a constant? My only idea was to use a generating function and ...
0
votes
1answer
50 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
0
votes
0answers
25 views

recursion $t(n)=\sqrt{2} \times \frac{tn}{2} +\log{n}$

I tried substituting $m=\log{n}$ $t(2^n)=\sqrt{2} \times \frac{t2^n}{2}+m t(m)= \sqrt(2) \times \frac{tm}{2}+m$ From here I got $\log {n}$ But with induction I proofed its $\sqrt {n}$
9
votes
3answers
83 views

How to prove that the recurrence $a_{n}=a_{n-1}+n^2a_{n-2}$ gives $(n+1)!$ without induction

Define the sequence $\{a_n\}$ by $a_{1}=2,a_{2}=6$, and for $n>2$, $$a_{n}=a_{n-1}+n^2a_{n-2}$$ show that $$a_{n}=(n+1)!$$ I know if we use induction,it is easy to prove it. ...
0
votes
1answer
30 views

Nonconstant solutions of discrete predator and prey model and Perron-Frobenius

Consider the discrete dynamical system given by $x_{n+1} = A x_n$, where $A = \begin {pmatrix} a & -b\\c &d\end {pmatrix}$ and $x_n = \begin {pmatrix} u_n\\v_n\end {pmatrix}$. Are there ...
0
votes
2answers
24 views

Solving a nonlinear recurrence relation

How does one solve a recurrence relation of the kind $u_{k+1} = u_k + u_{k-1} + a \cdot \cos(\omega k)$ for arbitrary $a > 0$ and $\omega > 0$?
1
vote
0answers
13 views

A 2-variable stochastic difference equation exhibiting 2 stable orbits with switching?

I have some social science data to which I would like to fit a stochastic difference equation in two variables. I will describe the dynamics of the system that I have observed. I am hoping someone ...
0
votes
2answers
27 views

Need help figuring out substitution with recurrence equation. [duplicate]

I need help with an Algorithm text book problem. The problem is the following T(n) = 2T(n/2) + n We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an ...
1
vote
2answers
65 views

Finding a Solution to a Equation that Ends up as a Weird Repeating Series

I need to find the solution to this equation that ends up in a weird repeating series. The equation in question is: $$ \ln(y)=\frac{K}{\alpha}+\frac {x^{2}}{2\alpha\sigma}+\frac{\ln(\ln(y))}{2\alpha} ...
1
vote
1answer
25 views

Variable coefficient difference equation I

Consider the difference equation \begin{align} n \, \phi_{n+1} &= (2 \, n^{2} + 2 \, n -1) \, \phi_{n} + (n+1) \, \phi_{n-1}. \end{align} It is seen that if $\phi_{n} = \Gamma(n+2) \, \theta_{n}$ ...
10
votes
1answer
482 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
0
votes
0answers
42 views

Substitution method for solving recurrences

I am new to math.stackexchange and I need help understanding Substitution method for solving recurrence. This is the original problem T(n) = 2T(⌊n/2⌋) + n Our guess is T (n) = O(n lg n) so we need ...
2
votes
1answer
64 views

How is Ramanujan's recurrence relation for his nested radical solved?

The Wikipedia article, here, describes in some detail the derivation of Ramanujan's famous nested radical, $$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}}.$$ In the Wikipedia article it provides a ...
2
votes
0answers
78 views

Number of unordered factorizations into $k$ distinct parts

Let $H_d(n)$ denote the number of distinct ordered factorizations of $n$ and $H_d(n,k)$ the number of ordered factorizations of $n$ into $k$ distinct parts. We have the following recurrence: ...
3
votes
1answer
25 views

$n$ dimensional determinant using recurrence relations

Find determinant $$D_n(a,b,c)= \begin{vmatrix} a & b & 0 & 0 & \cdots & 0 & 0 & 0 \\ c & a & b & 0 & \cdots & 0 & 0 & 0 ...
1
vote
1answer
52 views

Solving a particular 2d recurrence

I'd be interested in a solution to the recurrence \begin{align*} \frac{u\left[m,n-1\right]-u\left[m,n\right]}{h}+\frac{u\left[m-1,n\right]-2u\left[m,n\right]+u\left[m+1,n\right]}{h^{2}} & ...
-5
votes
1answer
37 views

Prove $a_n =\frac{ (n^2+n+6)}{2}$ [closed]

Let $a_n = 0$ and for $n>0$ let $a_n = a_{n-1} + n$. Prove $$a_n =\frac{ (n^2+n+6)}{2}$$ The only way I knew how to prove the recurrence relation is: $a_n = a_0+ nt$ but it doesn't work in ...
0
votes
1answer
27 views

How can we solve a multi-variable recurrence relation in closed form, when the number of terms is also variable?

Consider the formula $f(x, y) = f(x, y-1) + 2 \sum\limits_{i=1}^{x-1} f(i, y-1) $ The factor '2' makes this not expressible cleanly as $f(x, y) = f(x, y-1) + f(x-1, y)$, which is solved here using ...
1
vote
2answers
48 views

Formula for calculating a progressive sum

If we say that initially the addition is $1$, the sum $0$ and $d$ is constant of $5$. step 1) ...
4
votes
1answer
40 views

How many matches are played?

A tennis club has $10$ couples as members. They meet to organize a mixed double match. If each wife refuses to partner as well as oppose her husband in the match, then in how many different ways ...
2
votes
2answers
53 views

Linear Recurrence In Faster Time

I am trying to solve this linear recurrence using matrix exponentiation:- $$f(n) = 2f(n-1) - f(n-2) + c,$$ where $c$ is a constant. What I have come up with is this - Let the matrix $M$ be $$ ...