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

learn more… | top users | synonyms (2)

0
votes
2answers
88 views

Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or

A) Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or jogging at 4 miles per hour or running at 8 miles per hour; at the end of each hour a choice ...
0
votes
1answer
18 views

Proof by Induction Question - as part of Russo Dye Theorem

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$. How can i show this is true for ...
0
votes
1answer
24 views

Using Difference Equations to Solve Word problems

While I was studying about finite differences I noticed a question in difference equations.Does anyone knows how to solve this using difference equations? WORD PROBLEM Imagine you are to jump from ...
0
votes
1answer
28 views

Solution for $T(n) = 2T(\sqrt{n}) + log_2(n)$ [closed]

Solve for: $T(n) = 2T(\sqrt{n}) + log_2(n)$ with no base conditions.
0
votes
1answer
52 views

How to find explicit formula using backwards iteration

For this problem I tried to solve it by iterating downward so: an = an-1 - n an-1 = 2*(2an-2 - (n-1)) - n = 4an-2 - 3n + 2 an-2 = 2*(4an-3 - 3n + 2) - n = 8an-3 - 7n + 4 an-3 = 2*(8an-4 - 7n + ...
0
votes
1answer
23 views

How to solve $T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$

I need to solve this Recursion Relation:$$T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$$ Do you have any idea how? (I try to find another way instead induction). (We should get: $T(n)=\Theta(n\log n)$) ...
0
votes
1answer
30 views

Recurrence relation for the coefficients of the polynomial $p_n(x) = \prod_{i=0}^{n-1}(x-i)$

Let's consider the polynomials $$ p_n(x) = \prod_{i=0}^{n-1}(x-i)=\sum_{i=1}^{n} a_{n,i}x^i$$. for all $n \in \mathbb{N}$. If $n=1$, then $p_1(x) = x$ and $a_{1,1} = 1$. Since I know that: ...
0
votes
1answer
50 views

how to calculate a modified fibonacci via matrix exponentiation

If I modify the fibonacci recurrence to be the following way: f(0) = 1 f(1) = 1 f(N) = f(N - 1) + f(N - 2) + 1 Is it possible to represent this recurrence in a matrix equation similar to the one ...
0
votes
1answer
37 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
2answers
40 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
0
votes
1answer
32 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
0
votes
1answer
94 views

Solve the recurrence relation $x_{n+2} -3x_{n+1} + 2 x_n = n$

Solve $$x_{n+2} -3x_{n+1} + 2 x_n = n$$ when $x_0 = 1$ and $x_1 = 0$. I started with the homogen solution: $$r^2 -3r +2 = 0$$ So $$x_n^h = A1^n + B2^n$$ I know that $x_n = x_n^p + x_n^h$ But I ...
0
votes
2answers
39 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
0
votes
3answers
42 views

This recurrence relation will evaluate to?

T(n) = 2T(n-1)+n, n>=2 T(1) = 1 What will this recurrence relation equation evaluate to ? I used substitution method and found out that this relation takes the form 2^k T(n-k) + 2^(k-1) * ...
0
votes
1answer
55 views

Help with using Master Theorem on Floor/Ceiling Functions [closed]

I have to use the master theorem to find the asymptotic growth of this function in Big-theta notation. T(x) = T(⌈x/4⌉) + T(⌊x/4⌋) + √x How should I approach this ...
0
votes
1answer
49 views

Finding recurrence relation on a problem

I need a little bit help finding a recurrence relation. So it goes like this: "A one-sided pavement is being made with tiles that come in 5 different colors. There are 3 light colors (light-yellow, ...
0
votes
2answers
51 views

Recurrence Relation $T(n) = T(\frac{n}{2}) + \sqrt{n}$

$T(n) = T(\frac{n}{2}) + \sqrt{n}$ and $T(1) = 1$. Assume $n = 2^k$. $$T(2^k) = T(2^{k-1}) + 2^{k/2}$$ $$T(2^{k-1}) = T(2^{k-1}) + 2^{k/4}$$ ... $$T(2) = T(1) + 2^{k/k} $$ $$T(1) = 1$$ I'm just ...
0
votes
3answers
117 views

How would I show that Tn=3^n + 2 is a solution to the recurrence?

Would anyone be able to help me or give me some advice on the following problem: Consider the recurrence with $T_0 = 3$ and $T_{n+1} = 3T_n - 4$ for all $n \in \mathbb{N}$. How would I show that ...
0
votes
1answer
34 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
0
votes
1answer
25 views

How many partitions are there?

How many partitions are there for $\{1,\cdots,100\}$ for $3$ sets, $A,B,C$, such that $A$ cannot contain consecutive numbers ($\left|a-b\right|=1$) Anyway, I thought about using recurrence ...
0
votes
1answer
29 views

Why does the sign change here?

They give the recurrence relation as: $$T(n) − 4T(n − 1) + 3T(n − 2) = 0,\ T(0) = 0,\ T(1) = 2$$ And then they say it can be written as the following for $n > 1$: $$T(n) = 4T(n − 1) − 3T(n − 2)\ ...
0
votes
1answer
69 views

Find the difference equation for {2, 4, 16, 256, …}

Write a difference equation to represent the change during the nth interval as a function of the previous term in the sequence. b. {2,4,16, 256,...} I know that an= 22n but I can't figure out how to ...
0
votes
1answer
54 views

On the existence/applications of infinitely-nested functions

Inside a previous question, one particular nested function shown is the known tetration. This "kind" of arbitrary repeated functions has always intrigued me, because inside their properties lie so ...
0
votes
1answer
65 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
0
votes
1answer
93 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
0
votes
1answer
38 views

$\Delta^kn^\alpha$ converges monotonically to zero when $\alpha<k$

I am trying to prove that the $k$-th finite difference of the series $n^\alpha$ converges to zero monotonically as $n\to\infty$ when $\alpha<k$. The differential analogue is ...
0
votes
2answers
57 views

Closed form for recurrence relation

Is there a closed-form solution to the following recurrence: $$T(n) = T(n-1) + T(n-3)$$ If yes, what is it and how can it be proven/derived? If not, then why because a somewhat similar recurrence ...
0
votes
1answer
28 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
0
votes
1answer
40 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots $ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
0
votes
1answer
46 views

Limit of recurrence relation $x_k= f(x_{k-1})$ for an increasing function $f:[0,1]\to[0,1]$

Is there a standard result out there that gives the following? It looks graphically like it must be true, but I'd like to appeal to a known result if possible. Let $f:[0,1]\to[0,1]$ be a continuous, ...
0
votes
3answers
56 views

Recurrence relations for students of the third year of secondary school.

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here) ...
0
votes
2answers
51 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
0
votes
2answers
44 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
0
votes
1answer
73 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
0
votes
1answer
51 views

How often does $p^k$ divide the Fibonacci numbers?

I would like to know about the Fibonacci numbers $F_n = 1,1,2,3,5,8, \dots$ in $\mathbb{Z}/p^k\mathbb{Z}$. $$ \mathbb{P}[p^k \text{ divides } F_n ] = \frac{\#\{1 \leq n\leq N: F_n \equiv 0 \mod ...
0
votes
1answer
28 views

math notation of iterated function

I'm trying to determine the proper notation for the following loop I have written in computer code: Set x = 2 set y = 3 For z=1 to z=5 (increasing the value of z by 1 each ...
0
votes
1answer
14 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
0
votes
2answers
45 views

Domain and range transformation

How can I solve this recurrence relation using Domain and Range transformations: $$ \begin{array}{rcl} n^2 a_n &=& 5(n-1)^2 a_{n-1} +2 \\ a_0 &=& 0 \\ \end{array} $$
0
votes
2answers
49 views

Higher order recurrence relation

I have the following non-homogenous recurrence relation and I'm trying to solve it using characteristics roots method : $a_n = 10a_{n-1} -37a_{n-2} + 60a_{n-3} -36a_{n-4} +4$ for $n \ge4$ and $ a_3 = ...
0
votes
1answer
25 views

help me finding the limit of sequence question

A 1= 1 and {A n}=root[1 + {A n-1}] B 1= 2 and {B n}=root[2*{B n-1}] help me Since I am studying math recently I need person`s help
0
votes
1answer
23 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
3answers
70 views

How to find the particular solution of a second order difference equation

I am trying to solve the second order difference equation, ...
0
votes
2answers
247 views

Total Time a ball bounces for from a height of 8 feet and rebounds to a height 5/8

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
1answer
31 views

Simple recursion question

While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation: $$ {\rm P}\left(n\right) \geq 1 - \left[1 - {1 \over 2}\,{\rm ...
0
votes
2answers
45 views

If infinitely many points of a sequence are given, is it possible to find out the recurrence relation?

I was thinking about sequences and stumbled upon a concept. If infinitely many points of a sequence are given, is it possible to find out the recurrence relation? Please enlighten.
0
votes
1answer
114 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
0
votes
1answer
111 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
3answers
85 views

walking along the number line

Suppose you start walking along the number line from $0$ to $100$, moving $1$ position to the right in each step. There are some shortcuts $(i,j)$ where $i,j\in[0,100]$ and $i<j$. If you step on ...
0
votes
2answers
159 views

Upper and Lower bounds for the function

Please find the upper and lower bounds of the recurrence relations. $T(n)= 4T(n−2) + 6T(n-3) + 3^n $ if $n>=3$ $T(n)= 1 $ if $ n <=2$ I am confused. Thanks a lot :)
0
votes
1answer
47 views

Verify if T(n) = T(n/2) + log(n) - Recurrence Relation

I'm not sure if I'm correct, but could you please verify if this is right: $$\begin{align} T(n) &= T\left(\frac{n}{2}\right) + log_{2}(n)\\ T(n) &= T\left(\frac{n}{2^{i}}\right) + ...