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

learn more… | top users | synonyms (2)

4
votes
3answers
113 views

Can't solve a recurrence

I am trying to solve the following recurrence: $$T(n) = 9T(n/3)+n^2$$ If I use the master method, I get $n^2\log{n}$ But, I am trying to solve it using substitution. When I try solving it this way, ...
0
votes
2answers
16 views

What is the length of a polynomial taken to a power (multiplied by itself)?

Let's say I have a polynomial $B(x)$. Its length is $m$ (By which I mean, if you write out the sequence of $a_i$'s where $B(x) = \sum_{i=0}^{m-1} a_ix^i$ the length of that sequence is $m$.) So you'll ...
1
vote
0answers
15 views

Recurrence Relation / Difference Equation Problem

I am trying to solve the following recurrence relation, but I am doing something wrong all the time when trying to find the particular solution, and I cannot figure out what. ...
5
votes
2answers
61 views

A recurrence relation problem: $\frac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \frac 1 n$

I need to solve this recurrence problem to find $a_n$ $\dfrac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \dfrac 1 n$ It is what I tried so far: $$\log (\dfrac {a_{n-1}.a_{n+1}} {a_n^2}) = \log(1 + \dfrac 1 ...
0
votes
0answers
14 views

Find the explicit closed form for this recurrence relation

I was given an example problem for recurrence relation in closed form. I understand the asymptotic class of $T$; that part's easy. I don't understand how the derivation where $T(4) + (n-4)6$ makes ...
0
votes
0answers
19 views

Solution to functional recursion equation

What is solution to following recursion when $c,d\geq1$ fixed? $$F(2^r)=cF\Big(2^{r-1}\Big)+F(2^{r-\frac{1}{r^d}}\Big)?$$
0
votes
1answer
27 views

About solving a second order difference equation [duplicate]

Let $r>4$ be a positive integer. I want to solve this difference equation: $$u_{n+1}-r²(1+r²ⁿ⁺¹)u_{n}+r²r²ⁿ⁺¹u_{n-1}-2r²r²ⁿ⁺¹=0$$ but I have no a good idea to start.
0
votes
2answers
34 views

Recurrence Equation Solution / Difference equation - WolframAlpha

I am given the recurrece equation $y_k-7y_{k-1}=5^k$ and found the (hopefully correct) particular solution to be $y_k^P=-\frac{5}{2}5^k$ WolframAlpha, however, gives the particular solution ...
-2
votes
1answer
25 views

Transformations solving recurrence with generating functions

Why is $\sum_{n ≥3} a_{n-1} z^{n-1}$ equal to $(A(z) − 1 − z)$? $\sum_{n ≥3}a_{n-2} z^{n-2}$ equal to $(A(z) − 1)$?
1
vote
1answer
35 views

Fibonacci numbers - how to get F from n [on hold]

That is, the equation of Fibonacci numbers is $F_n = F_{n-1} + F_{n-2}$, I want to write a function that takes $n$ and return $F_n$ so I want to mathematically get $F_n$ in terms of $n$ so the ...
-1
votes
1answer
32 views

Recurrence relation [on hold]

For $n = 1, 2, 3, . . . $ let $$I_n = \int_0^1 x^{n−1}/(2 − x) dx$$. Writing $$x^n = x^{n−1} (2 − (2 − x))$$, show that this sequence of numbers satisfies the recurrence relation $$I_{n+1} = 2I_n − ...
0
votes
2answers
40 views

How to deduce sum's result?

I was solving some tricky-task with algorithms and I obtained following reccurence: $$a_{k+1} = 4a_{k} + 16^{k}, a_{1} = 1$$ It's obvious that with given start condition: $$a_{k+1} = 4a_{k} + 16^{k} ...
0
votes
0answers
29 views

Does this tridiagonal system have a closed-form solution?

Let $$ A = \begin{pmatrix} a + c_1 & -b\\ -a & a+b+c_2 & -b\\ & -a & a+b+c_3 & -b\\ & &\ddots & \ddots & ...
3
votes
1answer
20 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
1
vote
1answer
46 views

Solve recurrence relation

Solve the following recurrence. First transform it to a simpler recurrence and then solve the new recurrence using generating functions or a characteristic polynomial: $f_n = f_{n−1} · f_{n−2}$ for $n ...
0
votes
1answer
16 views

Understanding the subsets without consecutive integers are counted with fibonacci numbers

I'm working my way though a section on Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients. There is an example that I do not understand. The part I'm having trouble with is ...
2
votes
1answer
15 views

Distinct Real Roots of $2^{nd}$ order linear homogeneous reccurence relation

I'm currently being introduced to $2^{nd}$ order linear homogenous recurrence relations for the first time. I was working through a first example in my textbook and came into some trouble. Here is the ...
1
vote
1answer
17 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
17 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
47 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
40 views

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

I have my solution to the recurrence relation crossed out for algos exam. Can someone explain where did I do a mistake? Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$ Let$$\lg n = m$$ ...
-1
votes
2answers
44 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$: ...
0
votes
0answers
15 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
58 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 ...
0
votes
2answers
29 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
46 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
26 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
22 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
21 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
14 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
20 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
29 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
66 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, ...
1
vote
2answers
34 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
23 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
37 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
35 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
43 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
41 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
43 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} $$ ...
3
votes
1answer
54 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
36 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
20 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
48 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
34 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 ...
-1
votes
1answer
25 views

Derive the following recurrence using the intersection diagram [closed]

Not sure how to go about doing the following homework question, any help would be great!
2
votes
1answer
39 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 ...