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

learn more… | top users | synonyms

0
votes
1answer
20 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
2answers
50 views

Use Bonnet recursion formula to prove by induction

Use Bonnet recursion formula: $P_{n+1}(x) = \frac{2n+1}{n+1} x P_n(x) - \frac{n}{n+1} P_{n-1}(x)$ to prove by induction 1) $P_n(1) = 1$ for all $n$ 2) $P_n(-x) = (-1)^n P_n(x)$ for all $n$ an for ...
0
votes
0answers
25 views

Need help with recurrence relations in general as well as specific problem

I am supposed to find the unique solution for a recurrence relation and I literally have no idea what to do. Here is what the professor did for us in class: \begin{align*} 3a_{n+1} - 4a_n &= 0 ...
0
votes
0answers
36 views

Total Time for a ball that bounces from a height of 8 feet and rebounds to a height 5/8 [duplicate]

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
1answer
36 views

Summation in recurrence

I search the entire forum and couldn't fint a solution to this. Can you please help me solve this recurrence equation? $$ T(n) = cn + \frac{4}{n^2}\sum_{k=0}^{n-1}T(k) $$
0
votes
0answers
25 views

need some guidance solving a recurrence

I've got this homework recurrence : $n^2T(n) = \sum_{k=0}^{n-1} 4T(k) + c \cdot n^3$ what I tried to do is to substitute n+1 to get : $(n+1)^2T(n+1) = \sum_{k=0}^{n} 4T(k) + c \cdot (n+1)^3$ and ...
0
votes
2answers
69 views

Total Time a ball bounces for from a height of 8 feet and rebounds to a height 5/8

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
1answer
28 views

Amount of numbers divisible by 3

Let $a_n$ be the amount of numbers consisting of $n$ digits from $\{1,2,3,4,5\}$ that are divisible by $3$ (giving an integer solution). I'm asked to proof that the following recurrence relation ...
0
votes
1answer
26 views

Simple recursion question

While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation: $$ {\rm P}\left(n\right) \geq 1 - \left[1 - {1 \over 2}\,{\rm ...
2
votes
1answer
54 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
1
vote
2answers
44 views

difference equation( recurrence relation)

Let $y_n$ satisfy the nonlinear difference equation: $$(n+1)y_n=(2n)y_{n-1}+n.$$ Let $u_n=(n+1) y_n$. Show that $$u_n= 2u_{n-1}+n.$$ Solve the linear difference equation for $u_n$. Hence find ...
0
votes
2answers
32 views

Solve Fibonacci-like linear recurrence equation

How to solve the following equation: $f(n) = f(n-1) + f(n-2) + 1$ My best guess is that it has something to do with Linear Recurrence Equation. I know how to do it without the constant $1$, which ...
0
votes
0answers
19 views

Generic Exponential curve base derivation

Alrighty so I am working on a computer program that forms ADSR envelopes including exponential curves for the attack, decay, and release segments. It uses the following equation for the exponential ...
0
votes
1answer
33 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
32 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
26 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
24 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
39 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
72 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
38 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
37 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
62 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
80 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
33 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
60 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 ...