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

learn more… | top users | synonyms (2)

0
votes
2answers
82 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
2answers
50 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
47 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
32 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
24 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
33 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
84 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
138 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
37 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
67 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
98 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
91 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 ...
1
vote
1answer
61 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
57 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
77 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 ...
2
votes
1answer
44 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
27 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
3answers
67 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
38 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
144 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
72 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
62 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
28 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
28 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
89 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) &= ...
4
votes
2answers
162 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
40 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
36 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
51 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
34 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
79 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
42 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
45 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$
1
vote
1answer
56 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
41 views

recursive-algorithm problem

I am not to sure were to begin Thanks
1
vote
1answer
60 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 ...
0
votes
0answers
173 views

Recurrence relation $F(n) = 2F(\sqrt n) + 1$

I'm stuck with the following recurrence relation: $F(n) = 2F(\sqrt n) + 1, n \in \mathbb{N}$ I considered $n = 2^{2^{k}}$ and then expanded the recursion and here is what I get $F(n) = F(2^{2^{k}}) = ...
0
votes
1answer
27 views

Recursion Tree: leaves at bottom level equals n^(log b / log a)?

My book says that the total number of leaves on the bottom level equals n^(log a / log b), with T(n) = a * T(n / b) + f(n). How do they come up with this? Say I have a function 3 * T(n / 4) + f(n) ...
1
vote
0answers
26 views

Did i multiply the sums correctly?

This is an extention to this question except i am unsure of whether i have done it correctly: $$ y'' = -y'(f(x) - r(x) y') $$ $f(x) = \sum_{n=0}^\infty s_n x^n$, $y = \sum_{n=0}^\infty a_n x^n$, and ...
0
votes
1answer
244 views

Use recursion tree to give an asymptotically tight solution of T(n)

Assume $T(1) = 3.$ Recurrence is $T(n)=T(n-3)+3n+1$ and I'm showing $\Theta$ bound by computing the exact running time. Starting off: $(Tn-3) + 3n + 1$ $(Tn-9) + 9(n-3) + 3n + 1$ $(Tn-18) + ...
0
votes
1answer
136 views

Tight bound for $T(n) = T(n^{1/2}) + 1$ [duplicate]

Can someone help me figure out the big-O for the recurrence relation $T(n) = T(n^{1/2}) + 1$? I didn't think the master theorem would work since it requires $T(n) = T(n/b)$... to have $b$ as a ...
0
votes
1answer
117 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...
1
vote
0answers
90 views

solve third order scalar using 3 by 3 matrix recursion

Suppose I have something like the following: $$t(n+2) = 3t(n+1) - 2t(n) + t(n-1)$$ I do not want a complete solution to this question. All that I would like to know is how to convert this into a 3 ...
0
votes
2answers
109 views

Recurrence Relations With Exponents

Solve the following: $$a_n = 2a_{n-1} + 2^{n-1} , a_0 = 3$$ Workings: $a_n = 2a_{n-1} + \frac{1}{2} 2^n, a_o = 3$ $a_n^{(h)} = 2a_{n-1}$ The characteristic equation is: $ch(x) = (x-2)$ ...
4
votes
2answers
116 views

Of fibonomials, pellonomials, and tribonomials, etc

I. Linear recurrence with order 2 Given the Fibonacci numbers $F_n$, we have $$\begin{aligned} &F_n+F_{n+1}-F_{n+2}=0\\[1mm] &F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm] ...
3
votes
0answers
46 views

Algorithms - Solving the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ [duplicate]

I have been trying to solve the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ for some time now. I only know substitution, recursion trees, and the master method (though it doesn't apply ...
2
votes
0answers
69 views

Generalizing the Fibonacci identity $F_{2n}=-F_{n-1}^2+F_{n+1}^2$

Using an integer relations algorithm, we get, $$F_{2n}=-F_{n-1}^2+F_{n+1}^2$$ $$6F_{4n}= -F_{n-2}^4-3F_{n-1}^4+3F_{n+1}^4+F_{n+2}^4$$ The pattern of the subscripts is clear. Expressing the ...
1
vote
2answers
54 views

Recurrence relation!

I want to know how to compute $H(n) = H(n-5) + \frac{n}5$ I know how to solve the recurrence relations whose difference between LFS and RFS is 1 (ex. $H(n) = H(n-1) + n$) but I have no idea how to ...