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

learn more… | top users | synonyms

1
vote
1answer
127 views

How to make recursive computation of $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ stable?

This is homework, so please only hints. We see that the recurrence $$I_n=\frac{1}{n}-\alpha I_{n-1}$$ can be used to compute the value of the integral $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ ...
1
vote
0answers
26 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 ...
2
votes
1answer
32 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 ...
1
vote
1answer
39 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$ ...
0
votes
4answers
40 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 ...
3
votes
2answers
72 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 ...
0
votes
1answer
25 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 ...
0
votes
0answers
17 views

Recursion on Matrix

We have a given matrix recurrence given, $ (\curlyvee_i,\curlyvee_{i-1})_{1\times3}= (\curlyvee_{i-2},\curlyvee_{i-3})_{1\times3}{\begin{bmatrix}A_{i-1}A_i+B_i & A_{i-1} \\B_{i-1}A_i & ...
1
vote
1answer
43 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 ...
28
votes
2answers
585 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
0
votes
1answer
7 views

Solve linear homogeneous recurrent relation with constant coef using generating functions

I have the following linear homogeneous recurrent relation which I have to solve using generating functions. $a_{n+2}-2a_{n+1}-3a_n = 0$ The generating function for this is: ...
0
votes
0answers
19 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
15 views

Recurrence relation-Summation of a series [on hold]

Sir, I have a Converging recurrence relation given as below, $-(\psi(n-1)) ...
5
votes
0answers
55 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 ...
0
votes
0answers
27 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
39 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} - ...
-1
votes
1answer
52 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
votes
1answer
41 views

Savings after $n$ years (using recurrence) [on hold]

A person deposits Rs. $250, 000/$ in a bank in a saving bank account at a rate of $8 \%$ per annum. Let $P_n$ be the amount payable after $n$ years, set up a recurrence relation to model the problem. ...
2
votes
3answers
89 views

Help with a proof that sequence of rational numbers $ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$ converges to an irrational, $\sqrt2$

I know that there are sequences of rational numbers with irrational limits. One in particular I've seen is $$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ with $a_0 =1$, This is clearly rational ...
6
votes
3answers
201 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$.
2
votes
4answers
112 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
2
votes
2answers
4k views

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

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
0
votes
0answers
32 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 ...
8
votes
1answer
213 views

Möbius function from random number sequence

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}. Then plug it ...
1
vote
0answers
25 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 ...
1
vote
2answers
168 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
4
votes
1answer
64 views

Expressing a Recursion in terms of factorials

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) = \Gamma(n+1)$$ ...
1
vote
1answer
17 views

Queuing theory-Multiple server (reducing simple recurrence formulas)

The equations given in 6.3 have been reduced which really eases the computation in further studies. But I tried to find the method of reducing these but I could not find a way at all. Any hints will ...
3
votes
4answers
59 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 ...
11
votes
3answers
245 views

Difficult Recurrence

I am trying to solve a Sangaku problem. The blue circles have radii one. The goal is to find the total area of all the other circles (the three sequences of circles repeat ad infinitum). I have ...
1
vote
3answers
83 views

Finding recurrence and an algorithm to represent it

You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy algorithm is not guaranteed to find the optimal way to ...
4
votes
2answers
453 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
1
vote
1answer
23 views

Is it possible that a randomized recursion has a nonzero probability of either converging or diverging?

I have very little "hands-on" experience with probability, but here is my context: I was looking at the random Fibonacci sequence: $$f_0=f_1=1, f_n=f_{n-1}+Xf_{n-2}$$ where $X$ is chosen randomly ...
1
vote
0answers
26 views

Complex numbers product and ratio, prove this relation.

Define a table $T$ as follows: $$\text{If}\; n\geq k \; \text{then} \; T(n,k) = (2+3 i) \sum _{i=1}^{n-1} T(n-i,k-1)+(5+7 i) \sum _{i=1}^{n-1} T(n-i,k) \; \text{else} \; T(n,k) = 0$$ Then take rows ...
6
votes
0answers
86 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$ to find nested radical

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. The background is to find nested radicals expressions of the form ...
1
vote
1answer
285 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
1answer
33 views

Evaluation of a Hankel-like determinant

I consider the following determinant (Hankel-like?) $$ [f_1,f_2,...,f_n]:=\begin{vmatrix} f_1 & f_2 & \cdots & f_{n-1} & f_n\\ n-1 & f_1 & \cdots & f_{n-2}& f_{n-1}\\ 0 ...
0
votes
0answers
18 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
1
vote
3answers
37 views

Why, intuitively, does the solution to a general linear recurrence relation make sense?

I reasoned through the solution to a differential equation, and $e^{\alpha x}$, for better or worse, seems to make sense. Each derivative sending the function to itself seems to suggest $e^{\alpha ...
2
votes
4answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
4
votes
1answer
95 views

Does this sequence consist of squares of integers?

Question: let sequence $\{x_{n}\}$ such $$x_{0}=0,x_{1}=1,x_{2}=0,x_{3}=1$$ and such $$x_{n+3}=\dfrac{(n^2+n+1)(n+1)}{n}x_{n+2}+(n^2+n+1)x_{n+1}-\dfrac{n+1}{n}x_{n}$$ show that:$ ...
6
votes
2answers
106 views

Finding non-negative integers $m$ such that $(1 + \sqrt{-2})^m$ has real part $\pm 1$.

I believe that the integers $m$ with $(1+\sqrt{-2})^m$ having real part $\pm 1$ are $0, 1, 2$ and $5$, but I'm having trouble proving it. Write $$a_m = \Re((1+\sqrt{-2})^m) = \frac{(1 + \sqrt{-2})^m ...
3
votes
1answer
48 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
0
votes
1answer
34 views

Prove that the elements of these two sequences are not null

Let $x_{n+1}=x_n+2y_n$ and $y_{n+1}=y_n-x_n$, where $x_1=1$ and $y_1=-1$. I tried proving by contradiction, I tried by induction, I got nothing. This is a question I had on an exam, I didn't manage ...
1
vote
1answer
238 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
1
vote
1answer
24 views

Recurrence relation and combinatorics

I am reading p.4 of the article http://mercercountymathcircle.files.wordpress.com/2014/03/recurrence_relations.pdf which consider the following problem: Find the units digit of ...
1
vote
3answers
299 views

Homework - Resolve the recurrence relation

What's the closed formula of this recurrence relation? $$a_n = a_{n-1}+2a_{n-2}+2^n \text{ with } a_0=1, a_1=2 $$
2
votes
1answer
48 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 ?
1
vote
1answer
40 views

Solving a (non-linear?) recurrence relation in 2 variables

I'm not sure if this problem is linear or not. Anyway, let me state the problem first: $$ \begin{align} P_n(a) &= \left(1 - \frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a) + ...
1
vote
0answers
26 views

Possible to determine if a more 'compact' solution to a linear recurrence exists?

Given a linear a recurrence relation. It is possible to express a solution in terms of summations, products, and the coefficients which appear in the recurrence. For example, in the case of a single ...