Recent content by sta|ker

  1. S

    Prove f(x) ∈ O(x^3) Using Big-O Definition: Homework

    Yes, the log base is assumed to be 2. Sorry, I forgot about that. Hmm, I guess I don't understand that technique then. I can do it using limits, but I guess I'll just have to review it until I get it.
  2. S

    Prove f(x) ∈ O(x^3) Using Big-O Definition: Homework

    Homework Statement Let f(x) = 2x^{3} + 3x\log{x}, prove f \in O(x^{3}) using the Big-O Definition. Homework Equations Big-O definition: f(x) \in O(g(x)) if |f(x)| \leq C|g(x)| and x \geq k where C and k are both positive integers. The Attempt at a Solution I basically set C=4 and k=4...
  3. S

    Bit Strings: Recursive Definition

    Ohh, I think I see. w represents the initial value, which would basically make everything I put wrong. What about the following: Basis: 0 1^{n} 0 \in A , n \in N Recursive Step: if w \in A, then 0 w 0 \in A Because, this would give: A = \{ 010, 00100, 001100, ... \}
  4. S

    Bit Strings: Recursive Definition

    Homework Statement Give a recursive definition for the set of bit strings \{ 0^{r} 1^{s} 0^{r} \| r, s \in N \}. Note the number of 0’s must be equal, but the number of 1’s may be different from the number of 0’s. Homework Equations N/A The Attempt at a Solution I believe this is: Basis...
  5. S

    Induction to prove then number of subsets with elements of 3

    Excellent, thank you very much for your patience! :smile:
  6. S

    Induction to prove then number of subsets with elements of 3

    Alright, I think I have it: We can obtain c by taking all the subsets with 2 elements in A and adding the extra element from B. So essentially c is the number of subsets with 2 elements in A. From a previous problem, we know the number of subsets containing 2 elements in a set is...
  7. S

    Induction to prove then number of subsets with elements of 3

    Hmm, I'm not sure I'm understanding this correctly: a represents the number of subsets containing 3 elements in a set A. b represents the number of subsets containing 3 elements in a set B. B is basically A with an added element, so B = A \cup \{x\} This means A \subset B, so there is a...
  8. S

    Induction to prove then number of subsets with elements of 3

    It won't change them, that's why I said b would be a+m. a is n and m is the number of subsets that do contain the new element. If you don't use the added element, it isn't going to change the amount of subsets with 3 elements. Regardless, it gave me an idea: Let a represent the amount of...
  9. S

    Induction to prove then number of subsets with elements of 3

    Alright, so we declare A as a set with n subsets of size 3. If we add one more element, and set it to B, we can say B is a set with n + m subsets of size 3. So, if we say the total size of A's subsets of size 3 is a = n, then we can say the total size of B's subsets of size 3 is b = a + m. I...
  10. S

    Induction to prove then number of subsets with elements of 3

    So: n subsets of 4 in A B = A \cup \{x_{4}\} A = \{x_{1}, x_{2}, x_{3}\} B = \{x_{1}, x_{2}, x_{3}, x_{4}\} So, n=1 for A, and n=4 (1 without x_{4}, 3 with x_{4}). The only pattern I see here is that there are 3 elements in A and 3 subsets with x_{4} in B. Though I don't think...
  11. S

    Induction to prove then number of subsets with elements of 3

    EDIT 2: Ok, just re-read again. So there are 3 sets of 3 in the extended set (lets call this B) that contain the new element, and 1 that doesn't. I'm still not sure of the relevance. I actually just re-read my assignment and our professor wants us to use Structural Induction, which is extremely...
  12. S

    Induction to prove then number of subsets with elements of 3

    Homework Statement Prove that a set with n elements has \frac{n(n-1)(n-2)}{6} subsets containing exactly three elements whenever n is an integer greater than or equal to 3. Our professor wants us to use Induction. Homework Equations P(n) = \frac{n(n-1)(n-2)}{6} n \geq 3 The...
Back
Top