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

learn more… | top users | synonyms (2)

2
votes
4answers
1k views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
3
votes
1answer
122 views

Proof for recursively defined sets

Language $L\subset \{a,b\}^*$ is such that: $\epsilon \in L$ $a \in L$ For any $x\in L$, $xb\in L$ and $xba\in L$ Nothing else in $L$. Im just learning recursive sets, but with that definition am ...
0
votes
1answer
79 views

Find solution using Recurrence relation [closed]

Find all solutions of the following recurrence relation $a_n =5a_{n–1} –6a_{n–2} +7n$. Please help me to find out the answer. Thanks in advance
1
vote
3answers
287 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 ...
0
votes
0answers
36 views

Analyzing convergence of a simple difference equation

I was playing with my calculator, had an arbitrary number on the screen, then pressed 1/x ,then sqrt, then 1/x, and so forth. I noticed it converged to 1.0 after a few back-and-forths. So, it occurred ...
0
votes
0answers
46 views

A simple recursion equation

Let $L_1=\lceil\log_2x\rceil$ where $x>0$, $L_i = \lceil \log_2L_{i-1} \rceil$ and let $T[1]=1$. What is the solution for the recursion equation $$T[x]=\sum_{i=1}^{L_1}\frac{xT[L_1-i+1]}{2^i}?$$
3
votes
4answers
330 views

If $x_1<x_2$ are arbitrary real numbers, and $x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $n>2$, show that $(x_n)$ is convergent.

If $x_1<x_2$ are arbitrary real numbers, and $x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $n>2$, show that $(x_n)$ is convergent. What is the limit? The back of my textbook says that ...
-2
votes
1answer
100 views

Solving recurrence $T(n) = 3 T (n/3) + n / \lg n$ [closed]

How to solve this relation? I mean the asymptotic solution?
1
vote
2answers
125 views

Express sequence in closed type

Given the sequence $a_n = \sqrt{2+a_{n-1}}$. Is there anyway to find a closed form for this sequence? Thank you for your time.
4
votes
1answer
109 views

Characterising spaces of linear recurrent sequences.

Let $K$ be a field and $\def\N{\mathbf N}K^\N$ the infinite dimensional space of all sequences of elements of$~K$. Any linear recurrence relation of order $d$ with constant coefficients $$ a_{i+d} = ...
7
votes
0answers
104 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
0
votes
4answers
2k views

Explicit Formula for a Recurrence Relation for {2, 5, 9, 14, …} (Chartrand Ex 6.46[b])

Consider the sequence $a_1 = 2, a_2 = 5, a_3 = 9, a_4 = 14,$ etc... (a) The recurrence relation is: $a_1 = 2$ and $a_n = a_{n - 1} + (n + 1) \; \forall \;n \in [\mathbb{Z \geq 2}]$. (b) ...
1
vote
2answers
131 views

Discrete math Exponential Generating Series

Solve the recurrence $y_{n+1} = 2y_{n} + n$ using exponential generating series. The given condition is $y_{0} = 1$. It is also noted that the equation is equivalent to $y_{n} = 2y_{n-1} +n -1$. I ...
1
vote
3answers
108 views

Recurrence relations with fractions

I have the following two equations: $$\alpha(t)=\frac{a}{b+\beta(t-1)}\\ \beta(t)=\frac{c}{d+\alpha(t-1)}$$ where $a,b,c,d$ are constants. Question is, is there an analytical form for $\alpha$ as ...
2
votes
1answer
101 views

Strange square brackets in recurrence equation

I have the following recurrence given: $$a_{0}=1$$ $$a_{1}=1$$ $$a_{n}=3a_{n-2}+3a_{n-1}$$ Why is that equal to something like this?: $$a_{n}=3a_{n-2}+3a_{n-1}-2[n=1]+[n=0 ]$$ What are those ...
6
votes
1answer
133 views

How to prove that this recursively defined sequence converges to $e$?

Let $a_1=0,a_2=1,$ and $a_{n+2}=\dfrac{(n+2) a_{n+1}-a_n}{n+1}$. Prove that $\lim_{n\to \infty}a_n=e$. I know that $\lim_{n\to\infty}\left(1+\frac1{2!}+\frac1{3!}+...+\frac1{n!}\right)=e$ and $a_n = ...
0
votes
1answer
78 views

Recurrence and Number of Ways to Make Change

I have the following problem where a shopkeeper makes change for $n$ cents by placing one coin at a time on the counter, keeping a running total; pennies, nickels, and dimes are available. Let $C_n$ ...
0
votes
1answer
68 views

Induction proof with no terms of sequence

The sequence $[x_n]$ is given by $x_1=1$ and $x_{n+1}=\displaystyle\frac{4+x_n}{1+x_n}$ for $n\ge 1$. Prove by induction that for $n\ge 1$, ...
1
vote
2answers
57 views

Recurrence relation problem, need help:)

I´m stuck on a problem. Can anyone help me? The problem: Find the recurrence relation to $$a_n=a_{n-1}+2a_{n-2}+\cdots+(n-1)a_1+na_0\;(\text{for }n\ge 1),\\a_0=1$$ I guess I have to compare ...
1
vote
1answer
54 views

Proof by Induction that if $s_1 < s_2$ and $s_{n+1} = \frac{s_{n+1} + s_n}{2}$ then $s_1 < s_n < s_3$ for all $n \ge 3$

Suppose$$s_1 < s_2$$ Use induction to show if $$s_{n+1} = \frac{s_{n+1}+s_{n}}{2}$$ for all $$n \geq 1$$ then: $$s_1< s_n < s_2, \ n \geq 3$$ I have no idea how to do this. I tried ...
1
vote
0answers
102 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
0
votes
1answer
44 views

Simple qustion about Induction

I need to prove T(N) = O(N) $T(n) = T([3N/4] )+ T([N/4] ) + 1$ I think a good way to solve is to prove that T(N) < N-1 Induction hypotysis: for N-1, prove for N: $T(n) = T([3N/4])+ T([1N/4]) + ...
1
vote
1answer
224 views

How to solve non-homogeneous recurrence relation?

The relation is $$T(n) = T(n-1)+T(n-2)-T(n-3)+1 \quad \quad (1)$$ I tried in this way but stuck at a point . Please Help $$T(n+1) = T(n)+T(n-1)-T(n-2)+1 \quad \quad (2)$$ Subtracting $(2)$ from ...
1
vote
2answers
377 views

what to do next recurrence relation when solving exponential function?

find gernal solution of :$a_n = 5a_{n– 1} – 6a_{n –2} + 7^n$ Homogeneous solution: $$a_n -5a_{n– 1} + 6a_{n –2} = 7^n$$ put $a_n=b^n$: $$b^n -5b^{n– 1} + 6b^{n –2} =0 \\b^{n-2} (b^2-5b^{} + 6b) =0 ...
2
votes
3answers
728 views

Monotone and Bounded Sequences: Proof

Say $s_1=1$ and $s_{n+1}=\frac{1}{5}(s_n+7)$ for $n\geq 1$. Prove that the sequence is monotone and bounded, then find the limit.
1
vote
1answer
125 views

Recursive and closed form solution for choosing $n$ pairs/triplets.. of $kn$ elements.

I stumbled apon an interesting question: How many ways are there to arrenge $kn$ elements into $n$ sets, $k$ elements each? There should be a recursive and closed form solution for $g_k(n)$. For ...
2
votes
2answers
78 views

If $a_{n+1} = u a_n+v a_{n-1}$, what recurrence does $a_{n+1}a_n$ satisfy?

If $a_{n+1} = u a_n+v a_{n-1}$ , what recurrence does $a_{n+1}a_n$ satisfy? You can assume that $u^2+4v > 0$. A starter question, which I have done some work on: If $a_{n+1} = 3 a_n - a_{n-1}$ , ...
2
votes
1answer
92 views

Questions about $\ln(z)$ recurrence and fixed points.

Define property $A_R$ for an analytic function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ for $|z|<R$ where $R$ is a radius. And $f(z)$ is analytic within the radius $R$ ...
0
votes
1answer
65 views

Recurrence Equation

I have a problem with this type of non-homogeneous equation. Find the solution of recurrence equation: $2 A_{n+1} = 3A_{n}-n+2$ $A_{0} = 1$ I know the idea behind the problem when the particular ...
2
votes
1answer
46 views

Question about fixpoints and zero's on the complex plane.

Define property $A$ for an entire function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ $2)$ $f(z)=z$ has exactly one solution $=>z=0$ (follows from $1)$ ) $3)$ $f(z)$ is not a ...
1
vote
1answer
66 views

Inequality With Recurrent Relation

$a_{1}=1$, $~$ $a_{n+1}-a_{n}=\sqrt{\dfrac{a_{n+1}^{2}-1}{2}}+\sqrt{\dfrac{a_{n}^{2}-1}{2}}$ , $~$ $a_{n+1}>a_{n}$ Prove that $~$ $\displaystyle\sum_{k=1}^{\infty}\frac{1}{a_{n}}<e$
1
vote
1answer
119 views

Proving the recurrence relation $xL_n'(x) = n l_n(x) - n L_{n-1}(x)$

How can I prove the following recurrence relation for Laguerre polynomials eqn $(11)$. $$xL_n'(x) = n L_n(x) - n L_{n-1}(x)$$ I managed to show that the following which seems to be true. I put all ...
57
votes
3answers
1k views

How prove this nice limit $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

Nice problem: Let $a_{0}=1$ and $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Show that ...
2
votes
4answers
65 views

Closed form solution to simple recurrence

I have this recurrence : $$f(i) = \begin{cases} 0 &i=0\\ 1 &i=M\\ \frac{f(i-1) + f(i+1)} 2& 0 < i < M \end{cases}$$ I have guessed that $$f(i) = \frac i M$$ and proved it via ...
2
votes
2answers
224 views

Solving $ T(n) = 1 + 2( T(n-2) + T(n-3) +\cdots+T(0) ) $

I have the following recurrence relation which I have obtained from an algorithm: $$ T(n) = 1 + 2( T(n-2) + T(n-3)+\cdots+T(0) ) $$ with base case $T(0) = 1$ and $ T(1) = 1 $ I would like to be ...
0
votes
1answer
55 views

Show that this is a general solution of the difference equation

I am currently doing my homework and have been struggling to pass this question: The difference equation Un = Un-1 + Un+1 is a discrete model for the equilibrium heat distribution along a straight ...
33
votes
5answers
1k views

How much weight is on each person in a human pyramid?

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of ...
5
votes
2answers
124 views

Why should we suspect that the recurrence $T(n) = T(n-1) + n(n-1)$ satisfies a polynomial identity?

In the question Algorithms: Recurence Relation, the author asked about the recurrence relation $$T(n) = T(n-1) + n(n-1)$$ and one of the answers proposed assuming $T(n)$ is polynomial, then ...
1
vote
4answers
71 views

Algorithms: Recurence Relation

Can someone please help me solve this recurrence relation using back substitution method: $$T(n) = T(n-1) + n(n-1)$$ Base case is T(1)=1. Also, what is the asymptotic notation? Explanation of steps ...
2
votes
1answer
64 views

recurrence relation dependent inversly on n

Is there any efficient way to solve $F(n)=F(n-1)+1/n$ on $\mathcal{O}(\log n)$ time like we have matrix expo. for fibonacci series ?
0
votes
1answer
29 views

Stability of difference equation considering only positive values

I'm analyzing the stability of such system difference equation with the constraint that $y_n \geq 0$ $\forall n \geq 0$ : $y_n = B y_{n-1} + D y_{n-2} \enspace (1)$ Using variable transform, the ...
6
votes
2answers
1k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
5
votes
1answer
440 views

Deriving a recurrence relation

The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ ...
1
vote
0answers
69 views

How to solve the recurrence relation $f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$ to find a closed-form solution?

A friend of mine gave me a math problem whose answer turned out to be $$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$ for some fixed $p$. I'm trying to find a closed-form solution to the ...
2
votes
2answers
87 views

A Recurrence Equation From a Game

$a_n=a_{n-1}(a_{n}-a_{n-2}+1)$ The above equation is defined in $[0,m]$ st. $a_{0}=0$ and $a_m=1$. It turned up as I was trying to analyze a simple richman game. I have managed to solve the equation ...
1
vote
2answers
100 views

How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$?

How to solve the following recurrence relation $$f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$$ with the initial conditions $f_{1}(x)=x, f_{2}(x)=x^2-1$? The answer is that ...
0
votes
1answer
113 views

Getting the closed form solution of a third order recurrence relation with constant coefficients

This is part of the proof of finding the closed from solution of third order recurrence relation I know that the closed form will look like the following And this is the part of the proof I can ...
1
vote
2answers
91 views

Can I get a hint on solving this recurrence relation?

I am having trouble solving for a closed form of the following recurrence relation. $$\begin{align*} a_n &= \frac{n}{4} -\frac{1}{2}\sum_{k=1}^{n-1}a_k\\ a_1 &= \frac{1}{4} \end{align*}$$ The ...
0
votes
2answers
701 views

Finding the closed form solution of a third order recurrence relation with constant coefficients [duplicate]

How would you solve for the closed form solution of a(n) given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
0
votes
2answers
188 views

Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...