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

learn more… | top users | synonyms (2)

1
vote
1answer
75 views

How to find the basic reproductive number of a discrete SIS epidemic model

I have been following a textbook called Mathematical Models in Population Biology and Epidemiology. The SIS model is given by the system \begin{aligned} S_{n+1} &= \Lambda + S_n e^{-\mu} ...
1
vote
2answers
313 views

Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or

A) Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or jogging at 4 miles per hour or running at 8 miles per hour; at the end of each hour a choice ...
1
vote
1answer
53 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
1
vote
2answers
42 views

how many even number faced dice will be their if 99 dices roll for eternity with some condition

Consider a six ­sided dice with number from 1 to 6. Imagine you have a jar with 99 of such dices. You throw all dices on the floor so they all land at different numbers. You look at one dice at a time ...
1
vote
1answer
139 views

Proving a Recurrence Relation by induction

I have the Recurrence Relation: $ T(n)=T(log(n))+O(\sqrt{n}) $, and I'm being asked to prove by induction an upper bound. I'm also allowed for ease of analysis to assume $n=2^m$ for some $m$. So here ...
1
vote
1answer
39 views

Difference Equation, verify expression is solution to the equation

I am reading a book on Probability, and do not know how to solve this example question. Consider the following difference equation and initial condition(s). In each case, verify that the expression ...
1
vote
2answers
47 views

Solving recurrence with non constant coefficients

I am having a hard time to solve the following $a_k=\left(\frac{d}{2}\right)^{k-2}a_{k-2}$ where $d$ is a parameter and $a_0=1$ $a_1=d$. Will appreciate your help. Thanks!
1
vote
1answer
77 views

What type of series is this: $k^n + k^{n-1} + k^{n-2} + k^{n-3}+\dots$

I am wondering what type of series this this, where you have some constant (let's say 4) to the power of n, summed up where each new exponent keeps going $n-1, n-2, n-3, n-4, ...$ and so on. So, ...
1
vote
1answer
146 views

Using recursion tree to solve recurrence $T(n) = 3T(n/2)+n$

I am trying to solve the recurrence $T(n) = 3T(n/2)+n$ where $T(1) = 1$ and show its time complexity. $n$ can be assumed to be a power of $2$. So basically, I drew out the tree and found that: ...
1
vote
2answers
71 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
1
vote
1answer
162 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
1
vote
1answer
154 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
1
vote
1answer
28 views

Checking recurrence relation

Is there a way to check my recurrence relation, so I can confirm I did it correctly? $a_k = -4a_{k-1} -4a_{k-2}$ with $a_0 = 0$ $a_1= -1$ My answer: $a_n = 0(-2)^n - ½n(-2)^n$
1
vote
1answer
27 views

Identifying R1 and R2 when solving Recursion relations

We are learning to solve recursion relations. When I get this step, does it matter if I define $r_1$ as 5 or 2 in this example?
1
vote
1answer
72 views

Power Series of Recurrence

Let n be a Natural number. Define $\ S_n $ to be the set of compositions of $\ n $ where no part is equal to 2, and let $\ a_n = |S_n| $. It is trivial that: $$ a_n = [x^n] \frac{1-x}{1-2x+x^2-x^3} ...
1
vote
1answer
38 views

constructing the matrix associated with a recursive function

This problem arrives from the Tower of Hanoi problem. We know that the least number of moves required to move the tower from one point to another is $2^n- 1$ where $n$ is the number of discs in the ...
1
vote
1answer
298 views

How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same. Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
2answers
68 views

Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

I have the following equation: $$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$ A little investigation: $T(2^1) = 1 + 2d$ $T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$ $T(2^3) = T(2^2) + ...
1
vote
2answers
90 views

Recurrence relation $T(n) = T(n/2) + n\log(n)$

So I've been working on this recurrence equation and I'm stumped at the end. $T(n) = T(n/2) + n\log(n);\: T(1) = 1;\: n = 2^k$ and $\log $ is base $2$. $T(2^k) = T(2^{k-1}) + 2^k \log(2^k)$ ...
1
vote
1answer
42 views

How can I solve the particular solution of the following recurrence (recursive) relation?

Having $a_n = 3a_{n-1} + 2a_{n-2} + 3·2^{2n-1}$ $a_1 = 12$ $a_0 = 0$ I solved the homogeneous part and got: $a^{{h}}_n = 1/12·2^n - 1/12·1^n$ This is the particular solution that I need to ...
1
vote
1answer
32 views

Exponential growth with a constant

Some guy opens a bank account with an initial amount of $\$1,000$. Each month he deposits $\$200$ and the bank gives him a monthly interest of $6\%$. I want to find the closed formula. Given this, we ...
1
vote
1answer
209 views

The solution of recurrence $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$ is $O(n\lg n)$

Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$. Here's what I tried - Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot ...
1
vote
1answer
260 views

Segner's Recurrence Relation [closed]

Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it? I can't seem to understand why this formula works/is true. $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots ...
1
vote
1answer
66 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
1
vote
3answers
86 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 ...
1
vote
3answers
79 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 ...
1
vote
1answer
59 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
1answer
168 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 ...
1
vote
1answer
59 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 ...
1
vote
3answers
54 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
40 views

non-homogenous recurrence relation, with split boundary conditions

I have non-homogenous recurrence relation: $x_{t+1}=\alpha x_t+\beta x_{t-1}+\gamma$ with the following boundary conditions: $x_2=\alpha x_1+\gamma$ $x_{T}=1/2x_{T-1} +1/2$ Anyone know how to ...
1
vote
2answers
94 views

Towers of Hanoi recurrence relation

How would I do this recurrence relation?
1
vote
1answer
19 views

Sequence of integrals defined by recurrence

For a sequence of integrals defined as follows $F_0(x)=f(x)$ for some function $f(x)$, $F_n(x)=\int_0^x F_{n-1}(y)dy$ for all $n\geq1$, can we use change of variables to find a nice expression for ...
1
vote
1answer
26 views

recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...
1
vote
4answers
79 views

A sequence was defined by a equation

The sequence was defined by the equations: $${a}_{1}=a\left(\in R \right),{a}_{n+1}=\frac{2{{a}_{n}}^{3}}{1+{{a}_{n}}^{4}},n\geq 1.$$ show that $\left(a \right)$The given sequence is convergent. ...
1
vote
2answers
53 views

First order recurrence relation

I have to solve this relation: $$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$ (k is constant) How can I do it??
1
vote
1answer
95 views

How to convert linear recurrence to a tiling question

If I have some linear recurrence of form $$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$ How does this translate to tilings? For example the Fibonacci sequence is the same as ...
1
vote
3answers
63 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
2answers
50 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
1
vote
1answer
52 views

Solve the following recursive relation by using generating functions

$a_n - 9a_{n-1} + 26a_{n-2} - 24a_{n-3} = 0, n \ge 3, a_0 = 0, a_1 = 1,a_2 = 10$ I have tried solving it by the normal way, but I have no idea how to solve it by generating functions. Please give me ...
1
vote
2answers
43 views

How can I find a recursive relation for the following words?

if $d(n)$ is the number of words created by the alphabet $\{a,b,c\}$ of length $n$ that do not contain $abc$ term then write a recursive relation for $d(n)$. I have read the same questions but there ...
1
vote
1answer
36 views

set problem of integers

Consider the following set $F=\{F^0, F^1, F^2, \ldots\}$. This set consists of positive integers which satisfy the following properties: $F^0= F^1=1$ AND $F^n= F^{n-1} + F^{n-2}$ for all positive ...
1
vote
2answers
491 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
1
vote
1answer
51 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
1
vote
1answer
26 views

About the particular solution given an homogeneous solution in a recurrence relation.

If your recurrence relation's characteristic equation factorizes to $$(x+1)(x-5)^3 = 0$$ and $h(n) = 3+2n \implies f_p(n) = d_0+d_1n$ $h(n) = 7n+3^n \implies f_p(n) = ...
1
vote
1answer
34 views

Simple recursion question

While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation: $$ {\rm P}\left(n\right) \geq 1 - \left[1 - {1 \over 2}\,{\rm ...
1
vote
2answers
76 views

Recurrence relation for number sequence

Let $a_n$ be the number of sequences of $n$ numbers, consisting of $0's, 1's$ and $2's$, such that a number $1$ on the $j$-th place isn't followed by a $1$ or $2$ on the $j+1$-th place for $1\leq ...
1
vote
1answer
178 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
1
vote
2answers
67 views

Show that there is a unique sequence of positive integers $(a_n)$ satisfying $a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1 $

Show that there is a unique sequence of positive integers $(a_n)$ satisfying the following conditions. $$a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1$$ I approached the problem to find out, ...
1
vote
2answers
60 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?