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

learn more… | top users | synonyms

1
vote
3answers
35 views

Strategies for developing explicit formulas for nth term given recurrence relation?

I'm wondering if there's any general strategies to develop an explicit formula for the nth term when you're given a recurrence relation. For example, I'm given a recurrence relation: $a_{n+1}=2a_n+1$ ...
0
votes
0answers
24 views

General solution of the recurrence equation with real shifts

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
1
vote
1answer
17 views

Convergence and recurrence

I am asked to prove that $\sum\limits_{n=1}^\infty {\sin(n)\sin(n^2)\over n}$ converges using the following fact: Let $(a_n)_{n=1}^\infty$ be a bounded sequence. Then $\sum\limits_{n=1}^\infty ...
2
votes
1answer
32 views

Recurrence relation converting to explicit formula

Let $a_n = -2a_{n-1 }+ 15a_{n-2 }$ with initial conditions $a_1 = 10 $ and $a_2 = 70$. a)Write the first 5 terms of the recurrence relation. b)Solve this recurrence relation. c)Using the explicit ...
3
votes
1answer
61 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
3
votes
2answers
79 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
1
vote
2answers
57 views

number theory of coefficients in an infinite sequence of polynomials

EDIT: equivalent formulation by Hurkyl in comments: if $n$ is odd and $p^\nu \parallel n$ and $n > 2k,$ then $$ p^{(\nu + 2 + 2 k - n)} \; | \; \sum_j \left( \begin{array}{c} n \\ 2j \end{array} ...
4
votes
1answer
73 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
0
votes
2answers
29 views

How to get the characteristic equation from a recurrence relation of this form?

I've been getting the characteristic equation from relations of the form $$U_n=3U_{n-1}-U_{n-3}$$ Thanks to this question I made before: How to get the characteristic equation? Now, I recently ...
1
vote
2answers
31 views

Finding the limit of a recurrence relation?

I have a sequence defined by the relation $$x_{n+1} = \alpha x_n + (1-\alpha)x_{n-1}$$ for $n\geq 1$, and I want to find the limit in terms of $\alpha , x_0,x_1$. I tried to do this by setting up a ...
2
votes
3answers
30 views

How to Find Recurrence Relation?

I'd appreciate help in understanding how to approach/find a recurrence relation. For example, if we are given the following situation, how would one find a recurrence relation? A computer system ...
3
votes
2answers
75 views

Fibonacci General Formula - Is it obvious that the general term is an integer? [duplicate]

Given the recurrence relation for the Fibonacci numbers, $F_{n+1}=F_{n}+F_{n-1}$ with $F_0=1$ and $F_1=1$ it's obvious that $F_n$ is a positive integer for all $n$. Suppose instead we were given ...
0
votes
1answer
19 views

Show that, for all natural numbers m and n, we have 2Fm+n = FmLn + FnLm

Show that, for all natural numbers m and n, we have 2Fm+n = FmLn + FnLm, where F0, F1, ... are the Fibonacci numbers and L0, L1, ... are the Lucas numbers. The recurrence relation for Fibonacci ...
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
1answer
44 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
2
votes
2answers
31 views

A mixture of AP and GP

A battery loses $10$ mAh of after every hour when in use. The same battery loses $1\%$ of its current amount of charge every hour when not in use. Suppose that the battery is fully charged with ...
0
votes
2answers
24 views

Use induction to solve the recurrence relation..!!

I don't know how to start this problem. I just need someone to show me the first couple steps of doing the induction for this relation. c is a constant. $T(n) = T(n - 4) + c\cdot n^{1/4}$ Thanks for ...
2
votes
5answers
55 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
0
votes
0answers
33 views
1
vote
2answers
38 views

Recurrence relation for number sequence

Let $a_n$ be the number of sequences of $n$ numbers, consisting of $0's, 1's$ and $2's$, such that a number $1$ on the $j$-th place isn't followed by a $1$ or $2$ on the $j+1$-th place for $1\leq ...
1
vote
0answers
39 views

Mathematical function alike to primes

Note: I'm currently in a low level algebra class and have very little knowledge of some of the more complex mathematical concepts. That being said, I can probably figure out anything I don't know ...
1
vote
1answer
29 views

Techniques for solving recurrence relations using generating functions

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?
1
vote
0answers
36 views

Monotonicity of a recursively defined sequence $s_{n+1} = \sqrt{4s_n -1}$

I am trying to answer this question: Let $s_1 = k$ and $s_{n+1} = \sqrt{4s_n -1}$. For what values of $k$ will the sequence $s_n$ be monotone increasing? I know the definition of monotone increasing ...
0
votes
2answers
36 views

Solving for Recurrence Function

I was reading the following http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf notes on recurrence relation, page 2. A recurrence function for the Tower of Hanoi is given by ...
2
votes
1answer
52 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
1
vote
0answers
56 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
0
votes
1answer
20 views

Help with difference/recursion equation change of variable

I am in a self study of Dynamic Systems and am reading through David Luenberger's book and cannot seem to figure the following question out. Solve the difference equation using a change of variables ...
2
votes
2answers
55 views

Explicit formula for recurrence

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers. I'm wondering how to get explicit formula for recurrence like ...
3
votes
1answer
155 views

Estimating linearly independent solutions to third order recurrence relation

I'm trying to prove something about two linearly independent solutions; $a_n$, $b_n$, to a recurrence relation I have - specifically that $\left| \frac{a_n}{b_n} \right|$ is eventually monotonically ...
-1
votes
0answers
41 views

What is wrong with this induction proof for a closed form recursive function?

I need some help, I can't seem to find What is wrong in this proof, yet I'm not getting what I need. Anyone know? Prove by induction $2(S(2^{k-1})) + 2^k = 2(2^{k-1})k +2^k$, given that: $S(2^0 ) = ...
4
votes
0answers
46 views

Transform recurrence relation

Is it possible to transform following recurrence relation $a_n=4a_{n-2}-a_{n-4}$, $a_0=1$, $a_1=0$, $a_2=3$, $a_3=0$ so that it will have nonnegative coefficients? Number of terms, of course, can be ...
0
votes
2answers
27 views

Proofs by strong induction [duplicate]

I am trying to solve the following problem using strong induction, the problem is the following: For any positive integer $n$, let $T_n$ be the number $1$ if $n<4$ and the number $T_{n − 1} ...
0
votes
1answer
31 views

What is the recurrence relation of $T(n) = c \cdot T(n^{\frac{1}{2}}) + n$ when $c>0$ and is a constant? [closed]

Trying to figure our what is the recurrence relation of $T(n) = c \cdot T(n^{\frac{1}{2}}) + n$ when $c>0$ and is a constant? Thanks to all helpers!
0
votes
3answers
60 views

Recurrence of T(n) = T(n/3) + T(2n/3)

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
0
votes
2answers
33 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
2
votes
0answers
20 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
1
vote
2answers
40 views

Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction $$ {\rm ...
0
votes
0answers
16 views

Recurrence formula for orthogonal polynomials

Consider the recurrence formula: $P_n(x)=(x-c_n)P_{n-1}(x)-\lambda_n P_{n-2}(x)$ The problem consist on showing that $\xi_1<c_n<\eta_1$ where $[\xi,\eta]$ is the true interval of orthogonality ...
6
votes
3answers
300 views

Why computing Fatou coordinate is so hard?

I'm trying to make images of Fatou coordinate for some polynomial maps. If I'm not wrong there is no explicit general formula/method for computing Fatou coordinate near parabolic fixed point. Is ...
0
votes
0answers
17 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
6
votes
2answers
337 views

Recursive square root problem [duplicate]

Give a precise meaning to evaluate the following: $$\large{\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\dotsb}}}}}$$ Since I think it has a recursive structure (does it?), I reduce the equation to $$ ...
0
votes
0answers
56 views

Recurrence t(n)=csqrt(n)+n

I'm having some trouble with this recurrence. $T(n)$= c$T(\sqrt{n}$) +n This is how i tried to solve it: $2^m= n, n= \log m$ $T(2^m)=cT(2^{m/2})+2^m$ switching $T(2^m)$ with $S(m)$ gives us ...
1
vote
1answer
33 views

Recurrence Question with Ternary String

Problem: Find a recurrence relation for the number of ternary strings of length n that contain at least one 0. Ternary string only contains 0s, 1s, and 2s. Approach: Assuming that the length n is ...
1
vote
2answers
38 views

Reference Request: Difference Equations

I am taking a second course in calculus and came across sequences defined inductively, as in recursively. My teacher told the class that a general formula for the $n$th term can be obtained using a ...
2
votes
1answer
45 views

Expected Time for n Independent Prisoners to Escape

Suppose there are $n$ prisoners, and each day every prisoner independently has a probability $p$ of escaping. What is the expected length of time before all prisoners have escaped? Someone asked ...
0
votes
0answers
26 views

Multiplicative Inverse of a Power Series

For a formal power series $$F(x) = \sum p_i x^i$$ a multiplicative inverse of $F$ exists iff $p_0 \neq 0$. The inverse $\sum q_i x^i$ satisfies the recursion $$q_0 =\frac{1}{p_0}\\ q_{n} = ...
0
votes
1answer
54 views

Recurrence Relation with two variables

I am trying to solve the following recurrence relation: $T(a,b)=T(a-2^{b-1}+1,b) + T(a,b-1)$ where: $$T(a,-1)=0\\T(0,0)=0\\T(a,1)=1\\T(a,0)=1$$ I tried using Matlab and Wolfarmalpha however they ...
1
vote
4answers
73 views

Solving the recurrence relation $a_{n+1}=a_n^2$

How would one solve the recurrence relation $a_{n+1}=a_n^2$ for, say, $a_0=2$? The solution seems to be $a(n)=2^{2^n}$, but how would one get to that conclusion? Furthermore, how would one solve a ...
1
vote
0answers
39 views

Solution to a recursion relation.

Let $\beta >0 $. The question is to solve a following recursion: \begin{equation} P^{(j+2)}(\beta) = \frac{\imath}{2} \left[ \left((-1+\beta) j - 1\right) P^{(j+1)}(\beta) + ...
1
vote
0answers
30 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...