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

learn more… | top users | synonyms (2)

0
votes
1answer
43 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 ...
1
vote
1answer
51 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
105 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
34 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 ...
1
vote
1answer
146 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 ...
0
votes
2answers
41 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 ...
2
votes
1answer
239 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 ...
0
votes
1answer
38 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
2answers
60 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 ...
0
votes
1answer
30 views

Solving thus summation

$F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} (i > 2)$. A new number sequence $Ai(k)$ by the formula: $A_i(k) = F_i × i^k (i ≥ 1)$.I need to calculate the following sum: $A_1(k) + A_2(k) + ...
0
votes
2answers
45 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
135 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 ...
7
votes
3answers
390 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 ...
1
vote
2answers
97 views

$a_{n}=C \alpha^{n}$ where $C\in R$ a general solution to difference equation $a_{n+1}-\alpha a_{n}=0$?

Suppose $T(N) = 2 T(\frac{N}{2}) + N$, where $T(1) = 0$ and $N = 2^{n}$ where $n \in N$. I get $ \alpha ^{n-1} (\alpha -2) = \frac{n}{C}$, using the general difference equation formula. My sketch: ...
1
vote
3answers
366 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$ ...
3
votes
2answers
254 views

Recurrence relations on a continuous domain

While attempting to read Shannon's paper I came across the following (p. 3): suppose $N\colon \mathbb{R} \to \mathbb{R}$ is a function, which for some fixed (given) set of values $t_1, t_2, \dots, ...
3
votes
1answer
184 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
vote
1answer
28 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 ...
4
votes
1answer
83 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
0answers
263 views

Two variable recurrence relations

I'm interested in solving the following type of problem... Starting with a recurrence relation in multiple variables, for example: $$ v_{i-1,j} + v_{i,j+1} + v_{i+1,j} + v_{i,j-1} = 4v_{i,j}$$ with ...
1
vote
2answers
72 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} ...
5
votes
1answer
108 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 ...
3
votes
2answers
104 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 ...
23
votes
2answers
559 views

Is $\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin x\cdots\right)\right)=\frac4{\pi}\sum\limits_{k=0}^\infty\frac{\sin(2k+1)x}{2k+1}$?

We can see intuitively that $$ f(x)=\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin{x}\cdots\right)\right)\right) $$ is the square wave with period $2\pi$ and has the ...
1
vote
3answers
293 views

using the recurrence relation

A person deposits Rs. 10, 000/- in a bank in a saving bank account at a rate of 5% per annum. Let Pn be the amount payable after n years, set up a recurrence relation to model the problem. Also using ...
2
votes
3answers
229 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 ...
0
votes
1answer
167 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 ...
3
votes
2answers
98 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 ...
1
vote
2answers
70 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...
1
vote
0answers
75 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) = ...
2
votes
2answers
52 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 ...
2
votes
1answer
70 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)$?
0
votes
2answers
48 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 ...
1
vote
1answer
80 views

Prove any $k\in\mathbb{N}$ can be created using sum of $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$

I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition. My attempt was just bad... I've ...
0
votes
0answers
42 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 ...
2
votes
5answers
128 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
3answers
230 views

Recurrence relations problem

Don't understand why someone would assign problems that he hasn't reviewed... It's crazy... I ask for help and got that response lol If $S_{n+2} = 2S_{n+1} - S_n + 3$, what are the correct steps in ...
1
vote
4answers
77 views

How to solve this reccurence relation?

Let a,b,c be real numbers. Find the explicit formula for $f_n=af_{n-1}+b$ for $n \ge 1$ and $f_0 = c$ So I rewrote it as $f_n-af_{n-1}-b=0$ which gives the characteristic equation as $x^2-ax-b=0$. ...
0
votes
1answer
38 views

second order difference equation question

$y_{n+2} - 2y_{n+1} + 2y_n = 62^n$ sub $y_n= r^n$ then $y_{n+2}=r^{n+2}$, $y_{n+1}=r^{n+1}$ so $r^{n+2} - 2r^{n+1} + 2r^n = 0$ $r^n( r^2 - 2r + 2) = 0$ I got a problem here, I can solve for $r$, ...
1
vote
0answers
53 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 ...
3
votes
1answer
195 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
5
votes
3answers
297 views

How to solve this recurrence $T(n)=2T(n/2)+n/\log n$

How can I solve the recurrence relation $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$? I am stuck up after few steps.. I arrive till $$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} ...
0
votes
2answers
41 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 ...
0
votes
1answer
34 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
88 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 ...
4
votes
0answers
58 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
48 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} ...
1
vote
3answers
510 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
66 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
1answer
82 views

second-order difference equation

I have a second-order difference equation question. yn + 2 - 78yn = 23n^2 What is the value of root in auxiliary equation? I have tried searching for videos online but I don't really quite ...