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

learn more… | top users | synonyms (2)

1
vote
1answer
17 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 = ...
0
votes
0answers
25 views

How to solve recurrence relation $T(n)=2T(n/2)+4^n$ using characteristic equation method?

With change of variables $n = 2^k$ We get $$T(2^k) = 2T(2^{k-1}) + 4^{2^k}$$ which yields $$S(k) = 2S(k-1) + 4^{2^k}$$ I cannot go further. Here: ...
0
votes
1answer
33 views

Solution to recursion equation

Solve the recursive equation $$ T(n) = T(n-1) * T(n-2) $$ with $T(1) = a$, $T(2) = b$ How do I solve this algebraically? I unrolled the recursion and got a solution of $a^{f_n}b^{f_{n+1}}$, ...
0
votes
0answers
39 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
0
votes
1answer
46 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...
6
votes
0answers
94 views

Minimizing beginning terms of a Fibonacci-like sequence

For $ a, b \in \mathbb{Z}^+ $ such that $ a = b $ or $ 2a < b $, let $ f_{a, b} : \mathbb{Z}^+ \to \mathbb{Z}^+ $ be a sequence that satisfies the following three criteria: $$ f(1) = a, \\ f(2) = ...
0
votes
1answer
47 views

How to find explicit formula using backwards iteration

For this problem I tried to solve it by iterating downward so: an = an-1 - n an-1 = 2*(2an-2 - (n-1)) - n = 4an-2 - 3n + 2 an-2 = 2*(4an-3 - 3n + 2) - n = 8an-3 - 7n + 4 an-3 = 2*(8an-4 - 7n + ...
2
votes
1answer
97 views

Finding a more explicit way to express a coefficient in this summation

I am sorry about the vague title, i really don't know how else to ask the question. So i have came up with the following: $$ 1 = \sum_{k=0}^{n} \sum_{v=0}^{n} \frac{x^{n-k+1} T_{n+1,k+1} ...
1
vote
0answers
24 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
1
vote
1answer
35 views

Ways to fill a $4\times N$ box

Given the integer $N$, we need to tell how many ways exist to fill a $4\times N$ board with $1\times 4$ and $4\times 1$ size boxes. Example: for $N=4$ there are $2$ ways.$ $
0
votes
2answers
37 views

Recursive definition proof

I'm having trouble proving the following: $a_0 = a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$. Prove that all the terms $a_n$ are odd integers. It makes sense since an odd number is of the ...
-1
votes
1answer
25 views

How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$. How do I show that: $T(n)=O(n^2)$ Thank you!! (P.S. I hope it's OK to ask it, but I'm looking for the simple ...
0
votes
1answer
21 views

How to solve $T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$

I need to solve this Recursion Relation:$$T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$$ Do you have any idea how? (I try to find another way instead induction). (We should get: $T(n)=\Theta(n\log n)$) ...
0
votes
1answer
28 views

Recurrence relation for the coefficients of the polynomial $p_n(x) = \prod_{i=0}^{n-1}(x-i)$

Let's consider the polynomials $$ p_n(x) = \prod_{i=0}^{n-1}(x-i)=\sum_{i=1}^{n} a_{n,i}x^i$$. for all $n \in \mathbb{N}$. If $n=1$, then $p_1(x) = x$ and $a_{1,1} = 1$. Since I know that: ...
6
votes
2answers
87 views

Count with only certain digits allowed - And feel a fractal

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he ...
0
votes
2answers
53 views

Solving easy inhomogeneous second order recurrence equations

I know the method of solving the characteristic equation to solve homogeneous second order recurrence equations. Now there is added an inhomogeneous term $c$, a constant. I have seen many ...
0
votes
0answers
11 views

Let $g_n^k=p_{n+k}-p_n$, where $p_n$ is the $n$th prime. Does there exist $g_{k+1}^1=2$ such that $g_1^k,g_2^k,\ldots$ is a “Gilbreath sequence?”

Call $(S_i)_{i=1}^{\infty}$ a Gilbreath sequence if $1=\lvert S_2-S_1\rvert=\lvert \lvert S_3-S_2\rvert-\lvert S_2-S_1\rvert\rvert=\cdots$, i.e., if the sequence can be substituted for the primes in ...
0
votes
2answers
34 views

Solving recurrence relation $f(n) = f(\lfloor\sqrt n\rfloor) + 1; f(1) = 1, f(2) = 1$

As the title shows, I need help approaching a solution for recurrence relation: $f(n) = f(\lfloor\sqrt n\rfloor) + 1$ if $n\ge3$ with initial values $f(1) = 1$, $f(2) = 1$ I am particularly ...
0
votes
1answer
22 views

Painting a circular disk

A circular disk is divided into n sectors, each shaped like a piece of pie and all meeting at the centre point of the disk. Each sector is to be painted either red, green or blue in such a way that no ...
1
vote
0answers
34 views

Recurrence relation sequence (Hard)

I was wondering if this sequence was possible using two base cases? The sequence is $\{-1,0,1,3,13\}$ .. Ive came close by doing $(a_{n-1})^2+a_{n-2}+a_n-1$ which works for everything but the $1$. I'm ...
0
votes
1answer
32 views

Probability of a population increasing from size $N$ to size $N + 1$ in a time interval $(t, t + dt)$?

Let $\lambda$ be the birth rate and consider a time interval $(t, t + dt)$. If we have a population of size $N$ the probability of it increasing to size $N + 1$ within the interval $(t, t + dt)$ is ...
0
votes
1answer
25 views

$T(n)=T(n-1)+O(\log n)$ is $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

I have this Recurrence relation: $T(n)=T(n-1)+O(\log n)$ What is the solution? $T(n)=O(n^2)$ or $T(n)=O(n \log n)$ What I did is: I assume that $T(n)\le O(n^2)$ And that's bring me to $O(n^2)$, ...
1
vote
1answer
18 views

Help with nested intervals/sequences

I really do not understand nested intervals. For example, one of my homework problems is: Let $x_0 \in \mathbb{R}$ and $x_{n+1}=\frac{1+x_n}{2}$ for all $n \in \mathbb{N}$. Prove that $\lim_{n \to ...
0
votes
0answers
16 views

Recurrence Relation (sequence)

I'm trying to find the relation of {-1,0,1,3,13} i've came close thinking it was (an-1)^2+(an-2)+an-1 but i cant seem to get all 5 of my elements to match up. Any ideas on a solution would be ...
0
votes
3answers
45 views

How many bit Strings?…

I have trouble figuring out these types of problems. Could someone help me out, with the different ways to answer it? How many bit strings of length six contain three consecutive 1’s? P.S i thought ...
1
vote
3answers
35 views

recursive to explicit sequence

I am trying to find the explicit formula for the following recursion: $$a_{1}=3,\quad a_{n}=3- \frac{1}{a_{n-1}},\quad n \in \mathbb N,n>1$$ I tried in many ways but I cannot find any ...
2
votes
1answer
38 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
5
votes
1answer
81 views

Does the A001921 linear recurrent integer sequence always yield composite numbers?

Let $(a_n)$ be the A001921 sequence $$ a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$ Is it true that $a_n$ is always a composite integer for any $n\geq 2$ ? UPDATE : I now make a ...
1
vote
2answers
65 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
0
votes
1answer
25 views

Finding specific solution for second order nonhomogeneous recurrence equation

$\ x(n+2)−1/2x(n+1)+1/8x(n)=cos(nπ/2)$ Guess a solution -$\ Acos(nπ/2)+Bsin(nπ/2)$ where A and B are constants There were a question about this exact problem yersterday - Need help finding specific ...
0
votes
0answers
19 views

Solving this equation involving a floor

I'm trying to prove that the following recurrence is in $\mathcal{O}(n^4)$: $$f(x) = \left\{ \begin{array}{lr} 10 & ; n=10\\ 3f\Big(\Big\lfloor \frac{2n}{5} \Big\rfloor \Big) ...
1
vote
2answers
41 views

Question about recurrence relation problem.

solve the following recurrence relation, subject to given initial conditions. $a_{n+1} = 6a_n -9,$ $a_0 = 0,$ $a_1 = 3.$ Here is what I have done. $a_{n+1} - 6a_n +9 = 0$ $a_n = r^n$ $r^{n+1} ...
0
votes
2answers
23 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
45 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 ...
0
votes
1answer
29 views

Need help finding specific solution for second order nonhomogenous recurrence relation

$x(n+2)-\frac{1}2x(n+1)+\frac{1}8x(n)=\cos(n\pi/2)$ Guess a solution -- $Acos(n\pi/2)+Bsin(n\pi/2)$ where A and B are constants How do I go about this? Any help is appreciated
0
votes
0answers
40 views

How to solve the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$

It seems to me that the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$ has a tight upper bound of: $O(n^{1/2})$, however I am not sure how to prove this. Specifically, I would like to find an ...
3
votes
2answers
34 views

Problem to understand a recurrence relation

In Norris, Markov chains, I found the following: [...] a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ were both non-zero. Let us try a solution of ...
1
vote
0answers
42 views

Difference equation of second order system with zero

I saw from lecture notes that difference equation of a first order system is like this: (1) (2) (3) (4) 1. What happens between (3) and (4)? It looks like inverse Z-transform but according ...
4
votes
3answers
249 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
5
votes
3answers
65 views

Divergence of $a_{n+1}=\sqrt{2a_n+3}$?

I am wondering what I am missing from my proof. I would like to show that the limit of the sequence $$a_{n+1}=\sqrt{2a_n+3},\,\, a_1=4,$$ goes to $\infty$, as $n \rightarrow \infty$. Is there ...
2
votes
1answer
41 views

How do you prove uniqueness of solution of homogeneous linear recurrences?

I was following the MIT 6.042 course on OCW (that don't cover generating function on the lectures, sorry if the answer is easier by doing that method). Recall a linear homogeneous recurrences is of ...
0
votes
1answer
40 views

how to calculate a modified fibonacci via matrix exponentiation

If I modify the fibonacci recurrence to be the following way: f(0) = 1 f(1) = 1 f(N) = f(N - 1) + f(N - 2) + 1 Is it possible to represent this recurrence in a matrix equation similar to the one ...
0
votes
0answers
11 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
1answer
25 views

Linear recurrence by characteristic equation.

Consider the linear recurrence $a_n = 2a_{n−1} − a_{n−2}$ with initial conditions $a_1 = 3, a_0 = 0$. We have $x^2 − 2x + 1 = (x − 1)^2$. Thus $ x = 1$ and $a_n$ = $u(1)^n + v(1)^n$. Why do we get ...
4
votes
1answer
25 views

Good (asymptotic) upper bound for recurrence over divisors

I am looking for a good (asymptotic) upper bound on the following recurrence relation ($T(0) = 1)$: $$ T(n) = \left[ \sum_{1\leq d<n, d|n} T(d) \right] + 1 $$ Note that the recursion is only for ...
1
vote
1answer
38 views

How do I solve for the recurrence relation when P does not exist?

I'm using the method that my textbook uses. I first put the recurrence relation in the form of a matrix. After that I solve for the eigenvalues and eigenspaces to find P. Then they use P to find D and ...
0
votes
3answers
40 views

Prove that $S_n = 5^n - 1$

Use Strong Induction: $s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$ Prove that $S_n = 5^n - 1$ In regards to the first step, can I start at n=2? Not ...
1
vote
1answer
25 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 ...
0
votes
0answers
11 views

help solve this recurrence realtion

1.T(n) = T(n^(1/3))+3 and 2.T(n) = 2T(n − 2) + 2 By using Master theorem. For the second one I guess the solution is θ$(2^n)$.
1
vote
0answers
14 views

Complexities of Recurrences in the form $t(n) = t(\alpha n) + t(\beta n) + cn$

When considering recurrence relations, they are generally of a form similar to $$t(n) = t(\alpha n) + t(\beta n) + cn$$ and there are three cases to be considered for our values of $\alpha$ and ...