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

learn more… | top users | synonyms (2)

1
vote
2answers
112 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$ $...
1
vote
1answer
71 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 $(3+\sqrt{7})^{2014}+(3-...
1
vote
1answer
26 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
1
vote
1answer
71 views

Concerning a specific family of recursive sequences

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than $a_{n-1}$ of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before? Here are ...
1
vote
2answers
82 views

How do I find $\sum_{i=1}^n\frac{1}{x_i}$ where $x_i = x_{i-1} + \frac{1}{x_{i-1}}$

I have a recurrence: $x_n = x_{n-1} + \frac{1}{X_{n-1}}$. I need the value of n for which $x_n$ IS CLOSEST TO $2*x_0$, where $x_0$ is a positive integer. I tried the following: $x_1 = x_0 + \frac{1}{...
1
vote
2answers
40 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
3answers
70 views

Understanding a recurrence relation question.

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be ...
1
vote
1answer
89 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
1
vote
3answers
38 views

Given initial conditions and a recurrence relation, what is closed form in terms of n?

We are given that $a_0$ = 1000, and $a_1$ = 3000, and that $\forall n \geq 2$, $a_n = \frac{a_{n-1} + a_{n-2}}{2}$. What is the value when $n$? I've determined that, in the long run, it converges to ~...
1
vote
1answer
34 views

Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
1
vote
1answer
346 views

Number of n-digit ternary sequences with an even number of 0's and 1's

Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's? I know that you need to break it down into cases where the ...
1
vote
2answers
70 views

How can I get the following recursive relation that explained?

if $b(n)$ is the number of words created by the alphabet ${a,b,c}$ with $n$ length that each word has at least one $a$ character and after each $a$ there is no $c$ character write a recursive relation ...
1
vote
1answer
33 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
1
vote
1answer
29 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 {a_{n+...
1
vote
2answers
78 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} \...
1
vote
1answer
73 views

forming difference equation

there is a square with $60$ equal blocks. If a mosquito(bug)is set to fly starting at block $1$, it is equally likely to fly to other blocks. what is the probability after $n$ flies, the mosquito is ...
1
vote
1answer
53 views

How to convert this equation into a matrix form

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$ where $F(x)=1$ if $x<k$. $a,b,c,k$ are known (and positive) and $x$ is chosen. I want to solve this recurrence using a matrix but don't really know how to ...
1
vote
1answer
137 views

Solving Recurrence Relation by Generating Function Method

Im trying to solve an-7a(n-1)+10a(n-2) Im at the point where ∈aX^n-7∈a(n-1)X^n+10∈a(n-2)x^n=0 (terms of n are subscript) After this step it is given as replace the infinite sum by an expression ...
1
vote
1answer
898 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
1
vote
3answers
562 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
1
vote
2answers
70 views

solve the following recurrence exactly.

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)+t(n-4)&\text{otherwise.}\end{cases} $$ Express your answer as simply using the theta notation. I don't know where to go ...
1
vote
1answer
24 views

Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: rounding function)

I would appreciate if somebody could help me with the following problem Q: Let $(2+\sqrt{3})^n=a_n+b_n\sqrt{3}$ $(a_n,b_n,n\in\mathbb{N})$ . Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: ...
1
vote
1answer
63 views

Recurrence relation related proof

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .
1
vote
2answers
4k views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: $$P_n(x)=P_{n+1}'(x)-2xP'...
1
vote
1answer
185 views

Generating Function via Recurrence Relation

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated ...
1
vote
2answers
69 views

How to solve this mathematically

This is a question given in my computer science class. We are given a global variable $5$. Then we are to use keyboard event handlers to do the following: On event keydown double the variable and on ...
1
vote
2answers
403 views

Counting problem using exponential generating functions

From A Walk Through Combinatorics by Bona in the section on generating functions We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, ...
1
vote
2answers
111 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
1
vote
4answers
168 views

Find the solution to the following non-homogenous recurrence relation:

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} + a_{n+1} - 2a_n = n$ for $a_0 = 1$, $a_1 = -2$ I have found the homogenous part with the characteristic polynomial is $...
1
vote
2answers
2k views

Solving a recurrence relation using repeated substitution

So, basically I am having a big issue with this recurrence relationship: $$T(n) = T(n-1)+n, T(1) = 0$$ using repeated substitution I get down to: $$i=1, T(n-1) + n$$ $$i=2, T(n-2) + 2n - 2$$ $$i=...
1
vote
3answers
816 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: <...
1
vote
2answers
64 views

How does my professor come up with the recursive case in this algorithm analysis?

My professor gave us the following explanation for the recursive algorithm for finding the permutations of a set of numbers: When he has (T(m+1), n-1)) where does that come from? Why is it m+1 ...
1
vote
2answers
238 views

Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

I've been trying to find tight bounds for the equation: $$ T(n) = 2T(n/2) + n/\lg{n} $$ The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that ...
1
vote
1answer
88 views

Step by Step Second Order recurrence relations

Hi I have the following linear relation $S(n)= 2S (n-1)+3S(n-2)$ $S(1) = 3$ $S(2) = 1$ $S(3) = ?$ 1- I know I need to find $c_1$ & $c_2$ Which are $c_1 = 2 $, $c_2 = 3$ 2-I Know the ...
1
vote
2answers
149 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.
1
vote
1answer
3k views

Difference equations and Matlab (some working)

The difference equations below model the yearly populations of wolves and moose, measured in hundreds. The wolves kill the moose for food. $$\begin{align} x_n&=x_{n-1}-0.004x_{n-1}+0.002x_{n-1}y_{...
1
vote
1answer
105 views

Recurrence $a_{n+1} = xa_n$ using generating function

I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ ...
1
vote
2answers
141 views

Recurrence relation: $x_{n+1} = \frac 12 x_n + \frac 1 {x_n},$ [duplicate]

$$x_{n+1} = \frac 12 x_n + \frac 1 {x_n}, x_0 \neq 0$$ $$ a = \frac a2 + \frac 1a \Rightarrow a = \frac {a^2 + 2} {2a} \Rightarrow 2a^2 = a^2 + 2 \Rightarrow a^2 = 2 \Rightarrow a = \pm \sqrt 2$$ If ...
1
vote
5answers
89 views

solution of recurrence relation $x_{n+1} = \frac {1}{x_n + 1}$

$$x_{n+1} = \frac {1}{x_n + 1}; x_1 > 0$$ How to transform it into the form $x_n = $? I need the solution in order to check if it converges at any $x_1 > 0$.
1
vote
2answers
598 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with $...
1
vote
1answer
477 views

Using partial fractions to find explicit formulae for coefficients?

The set of binary string whose integer representations are multiples of 3 have the generating function $$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$ Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings ...
1
vote
2answers
127 views

Solve non-homogeneous linear recurrence

I have the following recurrence $$a_n - 3a_{n-2} + 2a_{n-3} = 9 (-2)^n$$ with initial conditions $a_0 = 0, a_1 = 1, a_2 = 26$. I wish to find an explicit formula for $a_n$. The characteristic ...
1
vote
1answer
243 views

Help with a different approach to extracting a polynomial equation from differences

It is well known that we can determine the degree of a polynomial can be found by finding when the differences are the same. i.e. if the second differences are the same, it is a polynomial of the 2nd ...
1
vote
2answers
97 views

Help me solve this recurrence relation

I'm trying to solve the recurrence relation $$a_n = (\lambda +\mu)a_{n+2}+\mu a_{n+3}.$$ with initial relationships of: $\lambda a_1 = \mu a_2$ $(\lambda +\mu)a_2 = \mu a_3.$ I found a site ...
1
vote
1answer
52 views

a recurrence equation interpolating linear and exponential

$f(n+1) = f(n) + f(n)^{a}$ where $a \in (0,1)$ and $n \ge 1$ with $f(1) = m$. If $a=0$, we see $f(n) = m + n - 1$ and if $a=1$, we see $f(n) = 2^{n-1}m$. So the recursion seems to interpolate ...
1
vote
2answers
39 views

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ if $s_1 = 0, s_2 = 0, s_3 = 1$ I have attempted to use $p_n = c2^{n-2} - d$ [where $h_n = A(3)^n$, but to no avail] - i ended up with $c=-...
1
vote
1answer
42 views

Details about a Recurrence Relation problem.

I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step: If $H_n$ is the number of moves it takes for n rings to be ...
1
vote
1answer
168 views

How many times can a student skip class in a 14 weeks semester?

In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
1
vote
2answers
144 views

Recurrence equation

Given the following recurrence equation: $T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$ How would you set this equation up in order to allow you to solve it using telescoping? Thanks in advance.
1
vote
1answer
94 views

Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$

$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$ I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...