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

learn more… | top users | synonyms (2)

0
votes
2answers
34 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
88 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
159 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
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
38 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
69 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
104 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
94 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 "...
2
votes
1answer
58 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} $$ ...
1
vote
1answer
80 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) = x(x+1)(x+2)$...
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
68 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
152 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 of ...
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
68 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 &\\ &=cn^2-2cn+...
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 ...
-1
votes
1answer
29 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) &= & g(...
6
votes
2answers
180 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 f(x)...
1
vote
0answers
37 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
56 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
35 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
1answer
96 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
44 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
46 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
57 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
59 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 sequence,...
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 $$\frac{\mathrm{...
0
votes
0answers
182 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
27 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
263 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) + 18(n-9)...
0
votes
1answer
150 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
126 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
98 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
110 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)$ $a_n^{(h)...
4
votes
2answers
122 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] &F_n^3+3F_{n+...
3
votes
0answers
47 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
56 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 ...
0
votes
0answers
32 views

How to solve this biparametral recurrence relation?

I have a problem that reduces to solving the following recurrence relation: $$X(2, 1) = 1, \ \ \ X(n, 0) = 0, \ \ \ X(n, k \geq n) = 0$$ $$X(n, 0 < k < n) = \frac{k-1}{n-1} X(n-1, k-1) + \left(...
1
vote
0answers
28 views

Did i generalize this series solution correctly?

$$ f(x) = \frac{y''}{p(x)y'} + r(x) y' $$ if all functions are expressed in their power series form, then: $$ y = \sum_{n=0}^\infty a_nx^n $$ $$ p(x) = \sum_{n=0}^\infty p_n x^n $$ $$ r(x) = \sum_{...
0
votes
2answers
32 views

Guidance on solving a recurrence relation

I am trying to solve the following recurrence: $T(1) = 2$, and for all $n\ge2$, $T(n) = T(n-1) + n - 1$ By using repeated substitutions, I was able to discern the following formula: $$T(n)=T(n-i) + ...
1
vote
1answer
36 views

Show $x_{r+1}$ defined as $x_{r}/2$ for $x_r$ even and $3x_{r}+1$ for $x_r$ odd goes to $1$ for all positive integer $x_0$. [duplicate]

Consider the following recurrence relation: $$x_{r+1} = \left\{\begin{matrix} x_{r}/2 &\text{if }x_r\text{ is even}\\3x_{r}+1&\text{if }x_r \text{ is odd}\end{matrix} \right. $$ I wrote ...
0
votes
1answer
32 views

How to simplify this logarithm?

I am looking at an example in my algorithms textbook, and I cannot seem to figure out how the following simplification occurred (my logarithm skills are a bit rusty): From this: $$\sqrt{n}c\sqrt{n}\...