-1
votes
0answers
14 views

Discrete Math Inductive Definition for Strings

Find an inductive definition for the following set of strings: $S = \{a^pbc^r : p\text{ is a natural number, and r is a natural number greater than }0\}$
0
votes
0answers
23 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
3
votes
1answer
98 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
3
votes
2answers
81 views

Proving that $xy = yx$ where $x$ and $y$ are both strings.

I am to prove that the following holds for any two strings $x, y \in \lbrace 0, 1\rbrace^*$ $xy = yx$ if and only if $\exists z \in \{0,1\}^*$ and $i,j \in \mathbb N$, such that $x = z^i$ and $y = ...
2
votes
0answers
43 views

Induction Problem ($n^2 ≤ 2^n$) [duplicate]

So I have this induction problem: $$n^2 ≤ 2^n \;\text{ for } \; n ≥ 4$$ I know the base case is ($n=4$) which checks out. I know the hyp is ($n=k$) giving $k^2 ≤ 2^k$. However, I am getting ...
1
vote
1answer
389 views

Using mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes

Use mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes. I'm familiar with mathematical induction proofs, but I haven't encountered one like this. ...
0
votes
3answers
55 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
2
votes
1answer
154 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
2
votes
2answers
1k views

meaning of 'Hypothesis' in simple terms?

could anyone please clarify me the meaning of the term 'hypothesis'? with relation to terms 'reasoning' and 'assumption' ? Many thanks
3
votes
2answers
669 views

Proving insertion sort using induction

A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion ...
3
votes
3answers
2k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
6
votes
1answer
590 views

Proof by double induction on strings (SOLVED)

I am truly baffled as to go on to prove this by double induction: http://i.stack.imgur.com/Zvrzt.png (snap shot of question) This question seems rather trivial on first glimpse, however trying ...