We have a robot that can move : (+2, - 1) (-2,  +1) (+1, +3) (-1, - 3) .  I have to show whether it will reach a certain position (x,  y)  I've done that on a computer,  recursively,  but  I can't  find  a recurrence formula.  Any ideas ?
122935
A robot moves on 2-Dimensional grid. It starts out at (0,0) and is allowed to move in any of these four ways: 1. (+2,-1) 2. (-2,+1) 3. (+1,+3) 4. (-1,-3) Prove that this robot can never reach position (1,1)
2933
Solve the recurrence relation  $$f(n) = 2f(n - 1) + f(n - 2)$$ with initial conditions $f(0) = a, f(1) = b$. (here a and b are fixed, arbitrary integers).  Can anyone show me how to solve this? a and b are fixed, arbitrary integers. Does it mean I can put any value for a and b?
30438
I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E).   Reach := {u} LastCardinality := 0 while LastCardinality &lt; |Reach| do   LastCardinality := |Reach|   Next := null   foreach i &lt;- Reach do     foreach j &lt;- V do       if(i,j) exists in E then         Next := Next + {j}   Reach := Reach + Next return Reach   So far I have got that the output needs to be Reach = Goal where Goal = {r | r exists V, there is a path from u to r}. I also have three invariants that I am pretty sure will help prove this.   Reach is always a subset of Goal and Next is always a subset of Goal. After an arbitrary K times through the while loop, for every t that exsits in V, if t has a path of length k+1 from u, then t exists in Reach If Reach is a subset of Goal before the while loop then LastCardinality &lt; |Reach|   I know that to finish up the proof, I need to prove termination, the invariants, and correctness but I have no idea how. I think I need to use induction on the while loop but I am not exactly sure how.   How do I proof those three characteristics about an algorithm?
49471
I am not able to solve the above recurrence relation which involves $n$. The initial conditions $a_0 = 1, a_1 = 2, a_2 = 3$, for $n \geq 0$. Please try to give closed form in terms of arbitrary $a_i \geq 1 $ for $i \geq 0$
80297
A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation:  $$T(n) = \sqrt n T(\sqrt{n}) + n$$  There are  and this question has already been asked here.  I was talking to my student about this problem and mentioned that it's quite hard to solve and is pretty dependent on the particular choices being made. As an example, I suggested this variant of a recurrence relation that was less simple to solve:  $$T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$$  The TA and I tried solving this recurrence for about an hour and a half without making any progress. Here are a few things we tried:   My approach to solving the initial recurrence relation was to draw out a recursion tree and notice that each level of the tree contributes $n$ to the total and that there are $O(\log \log n)$ layers, so the recurrence solves to $O(n \log \log n)$. When I tried doing this here, I noticed that the work per layer was no longer constant; instead, the top layer sums to $\sqrt{n}$, the second layer to $n^{3/4}$, the third to $n^{7/8}$, etc. We got stuck working with the summation $n^{1/2} + n^{3/4} + n^{7/8} + ...$. We tried using the iteration method to unroll the recurrence. With the original recurrence relation, this works out nicely; here, we got stuck at the same summation given above.   I'm completely stuck trying to figure out how to solve this recurrence relation. There's nothing riding on it per se - I don't need to solve it for any particular reason - but the fact that we arrived at it by a straightforward modification of a common algorithms problem set question makes it all the more enticing.  Any idea how to solve this recurrence?  Thanks!
33439
Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications"  Let P(n) be the number of strings not containg two containing two consecutive zeros or two consecutive ones.  I got the answer  P(n)=P(n-1)+2P(n-2)+2P(n-3)+...+2P(0) +2  but then the book says the sequence also satisfies the recurrence relation  P(n)=2P(n-1)+P(n-2). I am not able to understand this part.
6645
Given $a_1 \in \mathbb R$ . Consider the   sequence  $\{a_n\}$, which is recursively  defined by$$ a_{n+1} =\left\{\begin{array}{ccc}   \dfrac {a_n}{2} &amp;  \text{if $n$ is even,}\\  \dfrac {1 + a_n }{2} &amp;  \text{if $n$ is odd}.\end{array} \right. $$  Find the sub-sequential limit of this sequence.  I think  for  odd  $n$  the  limit  point will be   $l= \frac{1+l}{2}$ now  $2l = 1+l$  , here $ l = 1$  I don't  know the  limit point for0 even  $n$.  Please help me.
81620
In a game, you are standing somewhere and a move consists of either moving forward any number of steps, not moving at all, or moving $1$ step backwards. If you complete $n$ moves, find the number of sequences that end with you in your starting position and which never go behind your starting position. If the &quot;never go behind the starting position&quot; condition weren't there, the answer would just be $\binom{2n-1}{n-1}$. However I'm not on sure how to proceed from here.
9433
I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
39991
Solve the recurrence  $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$.  The final answer is $2^{n+1}-n-2$  Can anyone arrive at the solution?
93323
I am trying to solve the following recurrence relations using telescoping. How would I go about doing it?   $T(n) = T(n-1) + 1/n$ $T(n) = T(n-1) + \log n$   thanks
62731
Using some matlab (I know it's cheating) I found that: $$k=0 =&gt; Result=1$$ $$k=1 =&gt; Result=1$$ $$k=2 =&gt; Result=2$$ $$k=3 =&gt; Result=5$$ $$k=4 =&gt; Result=15$$ $$k=5 =&gt; Result=52$$ $$k=6 =&gt; Result=203$$  This sequence is puzzling...
99235
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 constant. I was wondering if anyone could shed some light on a method to approach this problem? (not looking for a solution)
48465
It turns out that the Fibonacci sequence satisfies the following explicit formula: For all integers $F_{n} ≥ 0$,  $F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1}]$  Verify that the sequence defined by this formula satisfies the recurrence relation $F_{k} = F_{k-1} + F_{k-2}$ for all integers $k ≥ 2$.
75653
If $0 &lt; r &lt; 1$ show that $r^n$ goes to $0$ as $n \to 1$.  If $|r| &lt; 1$ then  $r^2  &lt; r$  similarly $r^4 &lt; r^3 &lt; r^2 &lt; r$  so $r^n$ as $n \to +\infty$ will be equal to $1$  how can i finish this problem?
79621
I have solved the following recurrence relationship:  $T(1) = 1$  $T(n) = T(n-1) + n + 2$  so  $T(n) = \frac{1}{2}n^2+\frac{5}{2}n -2$  I am now trying to perform mathematical induction to prove this.  $Basis:$  $T(1)=1=3-2=\frac{1}{2} + \frac{5}{2} - 2 $  $Induction:$  $T(k+1) = T(k) + k+1 + 2$  $= \frac{1}{2}k^2 + \frac{5}{2}k -2 + k+1 +2$  $= \frac{1}{2}k^2 + \frac{7}{2}k +1$  What can I do next?
14842
Well if one looks at the formula of circular permutations $Pc = (n-1)!$  But as we come to that formula, I need a concrete example and an explanation.  Another thing, I have seen that when working with a bracelet, the formula changes. A concrete example please along with an explanation  Finally how the formula is worked when there are repeated elements that are permuted.  Thank you