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

learn more… | top users | synonyms

0
votes
0answers
25 views

n-th derivative of product

I am looking for a closed-form for the $n^{\text{th}}$ derivative of $$\beta_1 g_1 g_3 + \beta_2 g_2 g_3$$ if $$g_k^\prime = \alpha_k g_{k+1}$$ Here's what I have tried so far: \begin{align*} ...
1
vote
1answer
126 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
2
votes
0answers
57 views

How to solve this finite-difference equation?

How to solve the following finite-differences equation: $$f(x) = f(x-1) + f(x-\sqrt{2}), \quad x\in [\sqrt{2}, +\infty) \,?$$ Let's say $f(x) = f_0(x)$ for $x \in [0, \sqrt{2})$ is a given function. ...
1
vote
2answers
52 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
2
votes
0answers
44 views

Recurrence Relation with $n^{\frac{1}{2^k}}$ Square Root

I tried to solve this recurrence relation, like the following: $$ \\ T(n) = \begin{cases} T(\sqrt[2]{n}) + c, & \text{if }n \geq 2 \\ a, & \text{otherwise} \end{cases} \\\\ T(n) = ...
3
votes
2answers
134 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
57 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
64 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
645 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
52 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
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
85 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
37 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
108 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
29 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
273 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
138 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
29 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
77 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
61 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
88 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
30 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
50 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
68 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
35 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
94 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 ...
1
vote
1answer
50 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
49 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
90 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
280 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
59 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
38 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 ...