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

learn more… | top users | synonyms (2)

3
votes
2answers
142 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
1
vote
1answer
63 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
4
votes
2answers
67 views

A $n\cdot n$ square grid problem?

I thought of this problem when I was playing a game called BINGO with my friend. The game basically is like this: Suppose $2$ people are playing the game(can be played with any no of people though). ...
5
votes
3answers
709 views

Determining if a recursively defined sequence converges and finding its limit

Define $\lbrace x_n \rbrace$ by $$x_1=1, x_2=3; x_{n+2}=\frac{x_{n+1}+2x_{n}}{3} \text{if} \, n\ge 1$$ The instructions are to determine if this sequence exists and to find the limit if it exists. I ...
0
votes
1answer
172 views

Bounding error when iterating a function

If I am iterating some function $f$ that goes to infinity as x goes to infinity with error $o(g(x))$, for example, is there anyway to bound the error? To be more specific, if I have some sequence ...
2
votes
2answers
42 views

Solving a Recursive equation, wrong options? [closed]

This is a very simple recursive formula. Are the options provided wrong? $$ T(n) = T\left(\frac{n}2\right) + 2 $$ with $T(1) = 1$. What's the solution when $n=2^k$ ($n$ is a power of $2$)? The ...
1
vote
0answers
62 views

Explicit formula for inverse function for n-th partial sum of harmonic series

Originally, I was trying to work out an explicit formula for a function with the property that $f(x + \frac{1}{f(x)}) = f(x) + k$ for some $k$. This is inspired by a thing I did with a metronome ...
0
votes
1answer
36 views

$\Delta^kn^\alpha$ converges monotonically to zero when $\alpha<k$

I am trying to prove that the $k$-th finite difference of the series $n^\alpha$ converges to zero monotonically as $n\to\infty$ when $\alpha<k$. The differential analogue is ...
0
votes
0answers
26 views

analyticical solution of a Recurrence serie

I have the following recurrence relation: $L_N = L_x + \frac{1}{\frac{1}{L_r} + \frac{1}{L_{N-1}} }$ $L_0 = L_x +L_r$ If $L_x$ and $L_r$ are kept constant, I have no problem to find a solution to ...
0
votes
1answer
93 views

Finding the fixed points of a recurrence relation (and systems of) analytically?

How would I go about finding the fixed points of the following recurrence? $$X_n = 2X_{n-1}(2- 3X_{n-1}) + X_{n-1}$$ And therein, determining their stability analytically? Also, how does one find ...
1
vote
2answers
45 views

Prove by induction a formula for $x_{k+1}=\frac{x_k}{x_k+2}$, $x_1=1$

I have a IT Maths exam coming up and I just can't figure out this question. Any help would be appreciated thanks. A sequence of integers $x_1,x_2,\dots,x_k,\dots$ is defined recursively by ...
0
votes
0answers
25 views

Recurrence relation expressed as gamma funtions

Where can I find literature on solving recurrence relations expressing the nth term as a gamma function? I know this can be done for example with $\alpha_{k+1}=\frac{\alpha_{k}}{k+b}$ can be solved by ...
0
votes
2answers
40 views

Finding the position at n?

This dance asks every performer to follow a precise sequence of steps: • Stage 0 : First, get away from obstacles by setting up your starting point at position 0 • Stage 1 : Take one step forward ...
3
votes
5answers
110 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
1
vote
0answers
30 views

Asymptotic behaviour of two dependent recursive sequences

I have two sequences whose relation is described in the following recurrence relations: $ p_{k + 1} = p_k + \frac{1}{2s_k}$ $ s_{k + 1} = s_k + \frac{s_k}{p_{k+1}}$ (when $p_0=2, s_0 = ...
5
votes
5answers
274 views

Prove that the sequence with $T(0)=1$ and $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ is given by $T(n)=2^n$

$T(0)=1 \\ T(n) = 1 + \sum_{j=0}^{n-1}T(j) \\ $ Show that $T(n) = 2^n$. I know how to prove this by induction, but I would like to know how to show this using first principles. Edit: The way I want ...
8
votes
1answer
141 views

Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$

Question: Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$. Attempt: If I'm not mistaken this does not match any linear homogeneous pattern, nor ...
1
vote
1answer
30 views

Summation of series- substitution

If we have $\sum_{n=0}^{\infty}nf(n)=C, C\ne0\tag 1$, C is a constant, can we find a closed form for f(n)?. NB : Given condition is that $\sum_{n=0}^{\infty}f(n)$ converges to a constant value $K$ ...
2
votes
1answer
78 views

Recurrence - using power series

Could you help me in solving this recursion( a closed form ) using power series $\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$, where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$ HINT: We can think ...
1
vote
2answers
72 views

Summation of infinite series

If we know the series sum given below converges to a value $C$(constant) $$\sum_{n=0}^{\infty}a_n =C \tag 2$$ Can we generate following in terms of C. values of $a_n$ will tend to zero as n goes to ...
1
vote
3answers
63 views

recurrence relation with doubling stepping size

I have the following recurrence $$f(2n) = 2f(n)+n$$ By taking $f(1) = 1$ and then calculating a few values we can see that it grows in $$O(n \log n)$$ However is there a more algebraic way to come ...
2
votes
2answers
73 views

The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$

According to my notes,one solution of the recursive relation: $$P(n)=\sum_{k=1}^{n-1} P(k) P(n-k), \text{ for } n>1 \\ P(1)=1$$ is $\Omega(2^n) $. How do we conclude that this is one solution?
1
vote
3answers
77 views

Show that $I_{12}\ne-0.0189$

For $n=1,2,3,\ldots$, let $$I_n=\int_0^1 \frac{x^{n-1}}{2-x} \,dx.$$ The value taken for $I_1=\ln2$ is $0.6931.$ If the recurrence relation is now used to calculate successive values of $I_n$ we find ...
0
votes
2answers
53 views

Closed form for recurrence relation

Is there a closed-form solution to the following recurrence: $$T(n) = T(n-1) + T(n-3)$$ If yes, what is it and how can it be proven/derived? If not, then why because a somewhat similar recurrence ...
2
votes
1answer
89 views

General formula of Fibonacci look alike series

I'm trying to discover the general formula of a series defined with recursion: $$ a_1 = 2, a_2 = 3, a_3 = 4 $$ and $$ a_n = a_{n-1} + a_{n-3} $$ It looks like Fibonacci, but the starting points are ...
0
votes
2answers
42 views

Solving a recurrence relation. Check my answer

I have a recurrence relation: T(n)=4 for n<=2 T(n)=3T(n/3)+5 for n>2 So I began solving it, ...
0
votes
1answer
28 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
5
votes
5answers
108 views

Recurrence of the form $2f(n) = f(n+1)+f(n-1)+3$

Can anyone suggest a shortcut to solving recurrences of the form, for example: $2f(n) = f(n+1)+f(n-1)+3$, with $f(1)=f(-1)=0$ Sure, the homogenous solution can be solved by looking at the ...
0
votes
0answers
32 views

Recurrence relation, gambling type word problem

Problem: You decide to play at a Monaco casino. Every round you put 1 million on red. There's a 18/37 chance you will win, and a 19/37 chance you will lose the million. You keep playing until you're ...
2
votes
1answer
32 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
1
vote
1answer
53 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
1
vote
0answers
51 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
1
vote
2answers
83 views

How can i find if a given number occurs in a custom Fibonacci sequence?

Its a recent interview question from Amazon. For e.g. let starting numbers be $a$ and $b$, then third number will be $a+b$ and so on: forming recursion like: $F(n)=F(n-1)+F(n-2) , n\ge 2$ $F(1)=a$ ...
2
votes
1answer
44 views

Linear recurrence relation in Cantor-like sets

I have a linear recurrence relation $$a_i = \alpha_0 a_{i-1} + \beta(i)$$ Where $\beta(i) = \beta_0b_i$ with $b_i \in \{0,1\}^\mathbb N$ I know that $0 < \alpha_0 < \frac{1}{2}$, $\beta_0 = 1 ...
0
votes
3answers
72 views

Finding general formula for a recursion function

If we have a recursion relation defined as $a_n = 3a_{n-1}+1$ with $a_1=1$ then find the general formula for $a_n$ in terms of $n$ with a(1) = 1. So far I have: $a_n = 3a_{n-2}+1+1 = 3a_{n-3}+1+1+1 ...
0
votes
1answer
36 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots $ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
3
votes
2answers
99 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
2
votes
1answer
71 views

Limit of a Discrete Dynamical System

For the system defined below, the point by point evolution remains bounded for all $t$ so I could see that some sort of limit exists. However, the question is what sort of limit is it -- a single ...
0
votes
2answers
133 views

Why do we use the term “equivalent” with Operators but “equal” with Functions?

Why do we speak in terms of "equality" when we deal with functions but "equivalence" when dealing with operators? To elaborate: Two functions, f and g are equal to each other (denoted: f=g) if: ...
1
vote
1answer
52 views

Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are ...
0
votes
0answers
29 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
0
votes
0answers
31 views

Equality of a recurrent sequence and of a running maximum of another sequence

Let $\{a_n\}$ be a sequence of real numbers. Let $c,b$ be real constants. Define $$ L_{k,n}=\exp\left\{c\sum_{i=k}^n(a_i+b)\right\}. $$ Then it can be shown that $L_n=\max_{1\le k\le n}L_{k,n}$ is ...
4
votes
1answer
51 views

Is it possible to calculate the roots of the difference between successive terms of this polynomial series $\rm{P}_n (x)=x\rm{P}_{n-1}-r\rm{P}_{n-2}$

Consider the polynomial series defined by the following recursion formula: $$ \begin{align} &\mathrm{P}_0 = 1 \\ &\mathrm{P}_1 = x-r \\ &\mathrm{P}_n = x\mathrm{P}_{n-1} - ...
5
votes
0answers
93 views

Sum of infinite series defined recursively

Suppose $s$, $t$, and $\delta$ are constants satisfying $0<s<t<1$ and $\delta>1$. An infinite sequence $\{y_k\}_{k=1}^{\infty}$ defined as follows: The initial term, $y_1$, is the ...
7
votes
3answers
286 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
-1
votes
1answer
60 views

Initial values are lost (diff eq to Transfer function)?

I read eternal Julius O. Smith III and he says that $$x_{n-m} = z^{-m}X(z)$$ Particularly, difference relation $$y_{n} = y_{n-1} + x_{n}$$ is solved by by $$Y = z^{-1}Y + X = {X \over ...
1
vote
0answers
33 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
0
votes
0answers
40 views

Why does s = z+1?

What exactly is Laplace transform? motivated me to ask why unit function is 1/s by Laplace transform and 1/(1-z) by Z-transform? Both seem to be integrals of delta-pulse and secondary integration ...
3
votes
4answers
75 views

Elementary Proof of sum of alternating factorials

so I came across the rather interesting identity $$ \sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x-j)\right] \right] = x! $$ For positive integers ...
5
votes
1answer
80 views

Expressing a recursively defined function in terms of factorials or gamma function

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = ...