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

learn more… | top users | synonyms (2)

0
votes
0answers
37 views

I have a problem with solving this recurrence relation

I'm solving this recurrence relation: $$ a(n+2)+4a(n+1)+4a(n)\;\; =\;\; 7 $$ where $n\geq 0, \; a(0) = 1$ and $a(1) = 2$. My step is 1)solve for homogeneous solution \begin{eqnarray*} ...
1
vote
1answer
19 views

Recurrence relations and the empty set

I am currently setting up my variables and such for solving a problem and I am a bit confused about this little detail. The question is: How many ways can you make a number using only '1' and '2'? ...
1
vote
2answers
45 views

How to solve the following recurrence

I know others have already posted about this recurrence $T(n) = 2T(n/2) + n\lg n$ on the following these two posts: post1 and post2 However, the style in which they have solved them, is not one with ...
2
votes
3answers
56 views

How to solve nonhomgenous recurrence relation?

I'm studying this topic in advance and I'm working on textbook problems. The problem is simple : Solve the following recurrence relation a) $a(n+1)-a(n)=2n+3$, $n$ is greater than or equal to ...
2
votes
2answers
51 views

Count number of ways kangaroo can jump all points in interval and finish at last point

There is the problem from Flajolet and Sedgewick book "Analytical Combinatorics": "In how many ways can a kangaroo jump through all points of the integer interval $[1,n+1]$ starting at $1$ and ending ...
0
votes
1answer
48 views

Closed form for this 2 variable recurrence?

I'm trying to find a closed form for this two variable recurrence, but Wolfram Alpha does not seem to understand the input. $$ \begin{cases} a_{0,1} = 1 \\ a_{0,i} = 0 \quad \forall i\neq1 \\ ...
0
votes
0answers
45 views

How would I put these recurrence relation terms into a summation?

I was given these terms as part of a recurrence relation and I need to put it into a summation in order to solve it. $T(n)=2^{k}T\left(\dfrac{n}{2^{k}}\right) + 2^{k-1}T\left(\dfrac{n}{2^{k-1}}\right) ...
0
votes
1answer
28 views

Is there a formula for the summation of this form?

I am doing recurrence relations and I have done some work to get the summation $$\sum\limits_{i=0}^{k-1}16^{i}\left(\dfrac{n}{4^i}\right)^2.$$ I know that there is a formula if the summation was just ...
4
votes
3answers
136 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
31 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
20 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
105 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
25 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
45 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
1answer
85 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
37 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)$?
0
votes
2answers
47 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
37 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 & ...
0
votes
1answer
45 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
54 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
23 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
23 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 ...
2
votes
1answer
36 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
25 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
53 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
52 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
59 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
164 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
68 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
38 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
59 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
28 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
24 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
46 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
87 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
38 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
35 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
42 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
48 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
56 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
48 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
66 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
15 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
25 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 ...