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

learn more… | top users | synonyms (2)

2
votes
1answer
30 views

Logistic and Quadratic map

I am trying to understand the relation between a logistic map and a quadratic map. For example, how can you modify a logistic map for the quadratic map, i.e., modifying the logistic map ...
0
votes
1answer
19 views

Analysis of a non-recursive algorithm

I am working on a problem presented in Levitin and Levitin's book on algorithmic puzzles. Problem: The algorithm starts with a single square and on each of its next iterations adds new squares all ...
3
votes
1answer
52 views

Showing that $f_n$ is the number closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$ [duplicate]

I want to prove that the the $n$th Fibonacci number $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$. What would be a rigorous way to go about this? I assume I'll have to ...
3
votes
2answers
51 views

What is wrong with my solution for the recurrence $T(n)=2T(\sqrt{n})+\lg\lg n$?

an someone explain where did I do a mistake? Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$ Let$$\lg n = m$$ $$S(m) = 2S(m/2)+\lg m$$ We know (proved in class) that $$S(m) = O(m \lg ...
-1
votes
2answers
58 views

Solution of recurrence relation

I want to find a solution of $$ u(n+2) - 3u(n+1)+2u(n) = n, \text{ for } n \ge 0, u(1)=u(0)=1$$ Update: Solution using Joel idea: 1) multiply by $x^n$: ...
1
vote
2answers
154 views

Survival probability up to time $n$ in a branching process.

Let $\{Z_n : n=0,1,2,\ldots\}$ be a Galton-Watson branching process with time-homogeneous offspring distribution $$\mathbb P(Z_{n,j} = 0) = 1-p = 1 - \mathbb P(Z_{n,j}=2), $$ where $0<p<1$. That ...
0
votes
4answers
65 views

In the Collatz function, why does $2^k-1$ reach $3^k-1$ after $2k$ steps, and could it be used to find divergent trajectories?

If you start calculating the Collatz function from an integer of the form $2^k-1$, you will reach $3^k-1$ after $2k$ steps. So, it is possible to pick a starting value that continuously zig-zags ...
1
vote
2answers
35 views

In the Collatz function, why $3^{2k}-1$ and $3^{2k-1}-1$ always share the same trailing trajectory?

Why are the trajectories always the same for numbers of the form $3^{2k}-1$ and $3^{2k-1}-1$ for the Collatz function? For example, let $k = 3$. So, $3^6-1 = 728$ and $3^5-1 = 242$. The trajectories ...
0
votes
2answers
55 views

Solve recurrence equation $T(n)=2T(n-1)-4$

I got such recurrence equation which I cannot solve, I tried with mathematical induction, but I've got information, that this one is not linear and cannot be solve like that. And really have no idea ...
1
vote
1answer
32 views

System of Recurrence Relations

Solve the following System of Recurrence Relation: $$a_n = 2a_{n-1} - b_{n-1} + 2, a_0 = 0$$ $$b_n = -a_{n-1} + 2b_{n-1} - 1, b_0 = 1$$ Workings: $b_n - 2b_{n-1} = -a_{n-1} - 1$ $a_n = 2a_{n-1} - ...
0
votes
2answers
24 views

Newton's method for square root recurrence

Here is a screenshot from the book. Can you help me with understanding the last line with this approximation? I don't understand how it follows from the formula. Where the denominator has gone?:)
0
votes
1answer
23 views

Solving Recurrence using Master Theorem

I do not see why this recurrence T(n) = T(n/2)+ 2^n of case 3 of Master Theorem fullfills the additional condition a f(n/b) ≤ c f(n) as 2^(n*(1/2)) ≤ c 2^n can not be fullfilled for 0 < c ...
0
votes
1answer
19 views

With the characteristic equation, how do I get this solution?

There is one part of the characteristic equation I don't quite understand. If I've been given the following equation: $$ T(n)= \begin{cases} 1,\quad if\ n=1\\ T(n-1)+n+1 \end{cases} $$ Then, you ...
0
votes
2answers
26 views

How do you unfold this summation factor?

This is from Concrete mathematics page 27: If we apply $s_n = s_{n-1} a_{n-1} / b_n$ recursively, at last we will need to know $s_0$, but how did it disappear in eq. 2.11?
0
votes
1answer
45 views

Find asymptotic behavior of recurrence $T(n) =T(n-2) + 1/lgn$

I'm trying to solve this recurrence: $T(n) =T(n-2) + 1/lgn$. And I can't make progress on. What I did so far: $$ \frac{1}{lg(n - 2i)} = 1 \\ lg(n-2i) = 1 \\ n - 2i = 2 \\ i = \frac{n-2}{2} $$ $ n' ...
4
votes
2answers
75 views

Expected value of money left from a coin flipping game

Say we were to play a game. We started off with \$100 and kept flipping a fair coin. If it turned out heads, we won \$1, else our money got inverted. For example, if on the first flip we got heads, ...
0
votes
2answers
37 views

Solving the recurrence F(n) = 3F(n - 12). [closed]

I'm very much stuck and don't even know where to begin here, any help would be much appreciated. Thanks.
0
votes
1answer
33 views

On the calculus of recurrence relations using generating functions?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory: I don't understand what he's doing in the summations , I see that he mixed the general recurrence inside a generating ...
0
votes
1answer
44 views

Recurrence Relationf or a Quaternary Sequence

Find a recurrence relation for the number of quaternary (4base digits) sequences with no copy of $3000$ as a subsequence. Workings: First digit $0, 1, 2$ Proceed as normal: $3a_{n-1}$ If first ...
3
votes
1answer
36 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
1
vote
1answer
46 views

Recursive Definition of Is Equal To

I'm working through some of the intro problems in Sudkamp's Languages and Machines (basically an intro book to finite automata, context free grammars, Turing machines, etc), and I'm struggling a bit ...
0
votes
0answers
23 views

Test question regarding number of strings - please check my work

How many strings with length $n$ over $\{1,2,3,4,5\}$ are there such any even number is followed by its predecessor or its successor? My try: First, let $a_n$ be the number of such strings. If a ...
1
vote
1answer
53 views

Prove that $a_i\leq 0$ for $i=1,2,…,N-1$?

Let $a_0,a_1,...,a_N$ be real number satisfying $a_0=a_N=0$ and $$a_{i+1}-2a_i +a_{i-1}=a_{i}^{2}$$ for all $i=1,2,...,N-1$. Prove that $a_i\leq 0$ for $i=1,2,...,N-1$. I saw the problem in ...
1
vote
1answer
46 views

An algorithm for computing $\pi^{-1}$

Wikipedia: Borwein's algorithm claims Start out by setting $$\begin{align} a_0 & = \frac{1}{3} \\ s_0 & = \frac{\sqrt{3} - 1}{2} \end{align} $$ ...
2
votes
1answer
61 views

Words with A's and B's [closed]

Find the number of words of length $11$, where each letter is an $A$ or a $B$, and no two $A$s are consecutive. I got confused after making several cases and it looks like a recurrence relation... Any ...
0
votes
0answers
14 views

Need help in finding a mistake in my recurrence solution using Master Theorem

It was said during the class that $T(n)=2T(4n/5) + \mathcal O(n)$ is $\mathcal O(n\log n)$. I applied Master Theorem, but I did not get the same answer. My solution We have $$a = 2,\quad b = ...
2
votes
1answer
38 views

Multi Recurrence Relations

Solve the following recurrence relation: $$a_n = 3a_{n-2}+2a_{n-3} + 81n^2(2)^n+32(3)^n+4n+4$$ Workings: $a_n^{(h)} = 3a_{n-2}^{(h)}+2a_{n-3}^{(h)}$ $ch(x) = x^3 + 3x^2 + 2x$ $ch(x) = ...
0
votes
1answer
24 views

Why it is $O(n)$ running time when we separate problems on n/2 subproblems each recursive call (and we continue to work on one side)

So, I do not understand why it is $O(n)$ running time in the case when we have some $n$ elements and with each recursive call we separate our array by half and we continue working only on a one half ...
0
votes
0answers
10 views

Upper bound for $T(n) = T(2n/3) + t(4n/9) + O(n)$

I got $T(n) = O(n^{11/9})$ as the answer. I just wanted to confirm if this is a correct bound and is there any tighter bound possible than this.
0
votes
2answers
51 views

recurrence relations and generating functions - I need a hint

I need to find "closed form" to the recurrence relation given by: $a_{n+1} = \sum_{k=0} ^ {n} k a_{n-k}$ and $a_0 = 1$. I have tried using generating functions but it is no good. Any help would be ...
0
votes
1answer
36 views

Determining the fourth term of $c_k = kc_{k-1}^2$

What is the fourth term of the following recursively defined sequence? $c_k = kc_{k-1}^2$ for integers $k \ge 1$ and $c_0 = 1$. The possible answers are $12$ and $20$. I am not sure which one it is ...
2
votes
1answer
60 views

Divide and Conquer Algorithms

(a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for the number ...
0
votes
3answers
57 views

Discrete Math Recursion Question

I'm stuck and I was wondering if anyone could point me in the right direction Oh, Im so sorry! I forgot to state what I'm to do with it. It asks me to find a explicit formula for the recursion ...
0
votes
2answers
31 views

How to show that $T(n) = T(n-1) + \Theta(n)$ is in $\Omega(n^2)$

In the class we have been shown the way to prove that $T(n) = T(n-1) + \Theta(n)$ is in $O(n^2)$ $$ \begin{align} T(n)&\le T(n-1) +cn &\\ &\le c(n-1)^2+cn &\\ ...
0
votes
1answer
26 views

Derive Recurrence To Determine Bn

Here is a question that states Bn is the number of bit strings with length n>=1 that don't contain any maximal run of ones of odd length, they're all even. I know how to do the first question but not ...
0
votes
1answer
25 views

Determining the value of Tn with a board and bricks [closed]

I have this homework question and I'm not sure where to start or how to do either of the problems at the bottom of the question. Any help appreciated!
-2
votes
4answers
68 views

Solve The Recurrence Homework Question [closed]

The functions $f:\mathbb{N} \to \mathbb{N}$ and $g:\mathbb{N} \to > \mathbb{N}$ are recursively defined as follows: $$ \begin{array}{lcll} f(0) &= & 1, & \\ f(n) &= ...
3
votes
2answers
98 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...
0
votes
1answer
31 views

An ant is walking up a hill. at what x does he see the blade of grass.

've been working on this problem with Mathematica and by hand-help with either would be fantastic. The blade of grass is given by the line segment from (32,1/5) and (32,8). The 2D hill is given by ...
1
vote
0answers
22 views

Complexity of $T(n) = T(n-10) + \sqrt{n}$

I'm using the iteration method to find the complexity of the following recurrence (I can't use the master theorem because it doesn't match the MT form). $$ T(n) = T(n-10) + \sqrt{n} \text{ and } T(1) ...
1
vote
0answers
20 views

Deriving binomial distribution from a recurrence.

Let $X_n, n\geqslant1$ be iid random variables with distribution $\mathbb P(X_1=1)=p = 1 - \mathbb P(X_1=0)$. Let $S_0=0$ and $S_n=\sum_{i=1}^n X_i$, $n\geqslant1$. Let $q_{n,k}=\mathbb P(S_n=k)$, for ...
0
votes
1answer
22 views

Computation Operation in one Recurrence Relation

We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for ...
2
votes
0answers
66 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
1
vote
0answers
29 views

Sequence from generating function.

Consider the recurrence $$\mu_1=1, \mu_2=2, \mu_3=4, \mu_4=8, \mu_5=16, \mu_6=32 $$ and $$\mu_{n+6} = \mu_n + \mu_{n+1} + \mu_{n+2} + \mu_{n+3} + \mu_{n+4} + \mu_{n+5}, n\geqslant 1. $$ The generating ...
0
votes
3answers
41 views

Generating Function for a Recurrence Relation $a_n=a_{n-1} + n$

Find a generating function for $\{a_n\}$ where $a_0=1$ and $a_n=a_{n-1} + n$
0
votes
0answers
31 views

Sum of harmonic series depending on n

I am trying find a solution to a recurrence by using recursion tree and substitution method. My recurrence is $T(n) = T(n-1) + 1/n; T(1) = 1$. After drawing the tree I get the following sum: $1/(n-i)$ ...
1
vote
1answer
44 views

Solving a difference equation with several parameters

Let $r>4$ be a positive integer. Let us consider this difference equation: $$u_{q+1}=(r^{2q+1}+(c/a))u_{q}-(c/a)r^{2q-1}u_{q-1} +2c+d-(bc/a)$$ where $a,b,c,d$ are integers. I want to find a ...
4
votes
1answer
57 views

A reccurent sequence

Let $(a_n)$ a sequence such that: $a_1=1$ and $a_2=2$ and $a_3=3$ such that $a_n=\frac{a_{n-1}a_{n-2}+7}{a_{n-3}}$ show that $ a_n \in \mathbb{N} $ I tried to find a particular form of the ...
0
votes
0answers
40 views

recursive-algorithm problem

I am not to sure were to begin Thanks
1
vote
1answer
52 views

Closed expression for $y^{(n)}$ when $y' = ay$

I'm interested in tidying up the calculation of arbitrarily high order derivatives of a function containing an exponential. Although any function can have it's derivative expressed as ...