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

learn more… | top users | synonyms

0
votes
1answer
32 views

2nd Order Homogeneous ODE recurrence relation??

Doing some exam revision and have been stumped by this; the question asks you to find the recurrence relation satisfied by the coefficients. Attempt at solution: I have already found that there ...
0
votes
1answer
31 views

Hi guys, can anyone help with this recurrence relation problem?

I'm going through practice questions for my exams but this question has left me confused: The Bessel functions of integer order, Jn(x), are described by the generating function: Derive the ...
0
votes
1answer
25 views

Existence and Uniqueness of Solutions to First-Order Non-Linear Recurrence Relations

How do I go about proving the uniqueness of an existing solution to a recurrence equation of the form $$ a_{n+1} - f(n)a_n = 0 $$ ? Is there a theorem related to questions of uniqueness and ...
1
vote
0answers
23 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...
0
votes
1answer
40 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
0
votes
0answers
26 views

Recurrence Relation for the checkerboard problem

Im trying to come up with an accurate recurrence relation for the checkerboard problem given here (http://www.8bitavenue.com/2011/12/dynamic-programming-moving-on-a-checkerboard/). A recursive ...
0
votes
2answers
43 views

If infinitely many points of a sequence are given, is it possible to find out the recurrence relation?

I was thinking about sequences and stumbled upon a concept. If infinitely many points of a sequence are given, is it possible to find out the recurrence relation? Please enlighten.
1
vote
1answer
25 views

Recurrence relation to calculate the number of strings of $n$ characters that don't have consecutive vowels.

How can I find a recurrence relation to calculate the number of strings of $n$ characters (english alphabet, lowercase) that don't have consecutive vowels. It's clear that for $n = 1$ the result is ...
0
votes
2answers
28 views

Solving a Linear Recurrence Relation

I made quick progress on this, and then of course got stumped, so here's the problem: $$a_0 = -1, a_1 = -2, a_n = 4a_{n-1} - 3a_{n-2}$$ So, following the way I was taught to solve this type of ...
3
votes
2answers
65 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
1answer
26 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
1
vote
3answers
36 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
18 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
34 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
58 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
45 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
56 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 ...
0
votes
0answers
40 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
32 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
55 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
58 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
56 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
156 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
62 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
41 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
304 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 ...