-1
votes
1answer
49 views

Proof of a sequence with recursion

The problem asks to prove the following to be true. $$F^2_{n+1} - F_{n+1} F_n - F_n^2 = (-1)^n$$ Anyway, I've tried looking at this or similar proofs for going on an hour now, pretty much the only ...
3
votes
2answers
40 views

$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$ $0<c<1$ and $T(1)$ is constant. My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong. My guess is that $T(n) = ...
0
votes
0answers
23 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
0
votes
1answer
34 views

Find a formula for a sequence of the following character strings

Given strings: 0, 020, 0208020, 0208020180208020, 0208020180208020320208020180208020, ... I have to write a C++ program that computes the nth string. My problem is ...
0
votes
1answer
36 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
2
votes
1answer
48 views

Question about chebyshev polynomial

chebyshev polynomials are defined as such: $T_n(x)=cos(n*arccos(x))$ I'm asked to show that $deg(T_j(x))=j$ and that $T_0,T_1,T_2,...,T_n$ are an orthogonal basis of $\mathbb R_n[x]$. I think I can ...
0
votes
2answers
109 views

fill-in-the-blank induction proof

I'm stuck at homework task I'm working on. I would really appreciate some help. Here is the task: Let $f$ be a function on binary numbers defined recursively as follows. $f(0) = 1$ and ...
0
votes
1answer
156 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
0
votes
0answers
20 views

Recursion questions - How much series from $A=\{\dots\}$ have that which satisfy the conditions

I am trying to solve recursions problems to understand "how its works" and faced in 2 questions: How much series from $\{1,2\}$ have that the sum of the terms is $n$ How much series from $\{0,1,2\}$ ...
2
votes
2answers
117 views

recurrence relation homework question

This is a homework question let $a_n$ number of n digit quaternary $(0,1,2,3)$ sequences in which there is never a$ 0 $anywhere to the right of a $3$. Solve for $a_n$ bot sure how to go about this. ...
1
vote
1answer
46 views

Bit strings, $\omega$, $\lambda$ - need help interpreting and describing

Problem For these recursive definitions of sets of bit strings, show 5 elements from each set, and identify what set it is (in a few words). Attempt 1 Basis: $1 \in S_!$ Recursion: $\omega \in ...
1
vote
2answers
33 views

Recursive formulae involving a linear operator

Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...
1
vote
2answers
63 views

How to find an explicit formula for $d _ k$

Consider sequence $ d _ 1, d _2, d_3 $ $$d_k= \frac {d_{k-1}} {k + 1} $$ for all integers $k \ge 2 $ with the initial condition that $ d_1 = 1$. Find an explicit formula for $d_k$ for the $k^{th}$ ...
0
votes
3answers
1k views

Proof by induction for a recursive function $F(n) = F(n–1)+F(n–2)$

I'm having a lot of trouble with the following homework question: Consider the following recursive function: Base Case: $F(0) = 0,F(1) = 1$. Recursive Step: $F(n)=F(n−1)+F(n−2)$ for all ...
0
votes
0answers
561 views

Recursive definition for $S = \left\{{(a,b) \mid a \in \mathbb{Z}^+, b \in\mathbb{Z}^+ \text{ and } a + b \text{ is odd}}\right\}$

Give a recursive definition of each of these sets of ordered pairs of positive integers. [Hint: Plot the points in the set in the plane and look for lines containing points in the set. $S = ...
4
votes
1answer
141 views

Prove a function is primitive recursive

Help me please $f(x)=x+a$, where $a$ is a constant.
0
votes
3answers
1k views

Find a formula for a sequence of number

A sequence starts at $n=1$: $\{1, 4, 13, 40, 121, 364... \}$. Find an explicit formula that generates these numbers. Thanks a lot!
4
votes
1answer
334 views

Recursively Solving a Bellman Equation

Problem Overview I am to figure out $v_\pi$ of a certain Markov state. Given Information A set of actions, $a$ containing ${up, down, left, right}$ $v_\pi(12), v_\pi(13), v_\pi(14)$ (I am given ...
2
votes
2answers
68 views

Mathematical explanation of the output sequence

I have a recursive function that gives some sequence: def f(n): if n <= 0: return 0 else: return 1-(n%2)+f(n/2) Which returns a number. So I need ...
1
vote
3answers
134 views

Mathmatical representation of recursion function

Well i'm not so good at math, but i have the following task: Here's the code: ...