# Tagged Questions

For questions about approaches and techniques for discovering a proof, as opposed to writing it down clearly (which involves (proof-writing)). Should not be used unless the focus is on the technique of the proof instead of the solution.

763 views

### Fibonacci number identity.

How do I see that $f_{n+1}f_{n-1} = f_n^2 + (-1)^n$, $n \ge 2$, where $f_1 = 1$, $f_2 = 1$, and $f_{n+2} = f_{n+1} + f_n$ for $n \in \mathbb{N}$?
304 views

### Prove that $\log_9 15$ is irrational

Im having trouble with the following proof... Ill post what I have completed so far.. Prove that $\log_915$ is irrational. Ill attempt by contradiction assuming $\log_915$ is rational. So, ...
30 views

### How to prove that you cannot solve for x

I want to prove that $x$ cannot be solved for (besides the zero solution) in the equation $x^2=\sin(x)$.
52 views

39 views

### $\{a_n\} \to a$ iff $\limsup_{n \to \infty} \{a_n\} = \liminf_{n \to \infty} \{a_n\}$

It is clear that if $$\limsup_{n \to \infty} \{a_n\} = \liminf_{\to \infty} \{a_n\},$$ then $\{a_n\} \to a$, since we can just squeeze the terms in the middle. I understand that to prove the ...
219 views

### Proof by induction for “sum-of”

Prove that for all $n \ge 1$: $$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$ What I have done currently: Proved that theorem holds for the base case where n=1. Then: Assume that $P(n)$ is ...
46 views

### Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
25 views

### Use induction to prove that n! ≥ 2^(n−1) for for all integers n ≥ 1. [on hold]

Use induction to prove that n! ≥ 2^(n-1) for for all integers n ≥ 1. Hello everyone, I'm stuck on this problem right here $(k+1)! = 2^{(k+1)-1}$
34 views

130 views

### Prove the existence of the square root of $2$.

I am trying to prove the existence of the square root of $2$. I have some steps with a very vague explanation and I would like to clarify. The proof: Let S=\{x\in\mathbb R\mid x\geqslant 0 \text{ ...
848 views

### Proving that $C$ is a subset of $f^{-1}[f(C)]$

More homework help. Given the function $f:A \to B$. Let $C$ be a subset of $A$ and let $D$ be a subset of $B$. Prove that: $C$ is a subset of $f^{-1}[f(C)]$ So I have to show that every element ...
21 views

14 views

### Proof of optimal substructure for the “plus sign game”

First of all, I think there's no "plus sign game", I have just invented the name to describe the problem faster. Another thing: I thought to ask the question in these stack exchange's website because ...
225 views

42 views

### Let $A, B$ and $X$ be sets. Prove that if $A ∪ B ⊆ X$ then $A ⊆ X$.

I have just started learning set theory and I've been trying to learn how to do proofs, however I really can't figure out I've been trying to answer a simple one: Let $A, B$ and $X$ be sets. Prove ...
747 views

### What are the theorems in mathematics which can be proved using completely different ideas?

I would like to know about theorems which can give different proofs using completely different techniques. Motivation: When I read from the book Proof from the Book, I saw there were many ...
38 views

### How to formulate the requirements that a counterexample must satisfy?

Let $p_1, p_2$ and $p_3$ be three statements. Suppose now we know that if $p_1$ is true, then $p_2$ and $p_3$ are equivalent. That is, if $p_1$ and $p_2$ are true, then $p_3$ is true, and if $p_1$ ...
11 views

### Which Function is Big-O of the Other

Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true. If it is true, there exists ...
21 views

### Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one.

Let $X,Y$ be nonempty sets and $f:X\to Y$ be a function. Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one. My approach is by ...
68 views

### If a set is countable and infinite, there is a bijection between the set and $\mathbb{N}$

I'm trying to show that if a set $S$ is infinite and countable then there is a bijection $\varphi : S\to \mathbb{N}$. Since $S$ is countable, we know that there is an injection $f: S\to \mathbb{N}$. ...
23 views

### Basic question on equivalence relations.

Show that the following relation is an equivalence relation on the given set. $m \sim n$ in $\mathbb{Z}$ if $m \equiv n\,(\text{mod}\,6)$.
39 views

### Prove function space is linearly independent.

Let $V$ the space of all funcions $f:Ŗ\rightarrow R$. Prove that the ten functions defined by $x\rightarrow |x-1|$,$x\rightarrow |x-2|$,....,$x\rightarrow |x-10|$ are linearly independent. I need ...
2k views

### When has one sufficiently mastered an area of mathematics?

This is a rather soft question regarding the mastery of various mathematical subjects, such as undergraduate subjects. In particular, say, when has one mastered undergraduate analysis? Is it ...
73 views

### Proving the Ideal Generated by the Coefficients of $f(X)\cdot g(X)\in R[X]$ is $R$.

Let $R$ be a commutative ring with unity, and let $f(X),g(X)\in R[X]$. Assume the ideals generated by the coefficients of $f(X),g(X)$ are both $R$. Prove that the ideal generated by the ...
22 views

### Showing polynomials as products of roots

How do I show rigorously that any polynomial $a_nx^n+a_{n-1}x^{n-1}+...a_1x+a_0$ can be written as $a_n(x-b_1)(x-b_2)...(x-b_n)$ for real $a_i$ and real or complex $b_i$
117 views

### Polynomial tending to infinity

Take any polynomial $(x-a_1)(x-a_2)\ldots(x-a_n)$ with roots $a_1, a_2,\ldots,a_n$ where we order them so that $a_{i+1}>a_i$ is increasing so $a_n$ is the biggest root. It doesn't matter whether ...
73 views

### Is this a valid proof of this math challenge problem?

From a fixed point P not in a given plane, three mutually perpendicular line segments are drawn terminating in the plane. Let a, b, c denote the lengths of the three segments. Show that ...
584 views

### Equivalent systems of Linear equation

I've just begun to re-learn linear algebra because is so important, the book that I chose is naturally the Hoffman's for a lot of reason. Well, In the first chapter I'm stuck with the following, ...
33 views

### Straight line through $(a,b)$ with slope $m$ is the graph of the function $f(x) = m(x-a) + b$

Spivak's Calculus Chapter 3 Problem 6 says: Show that the straight line through $(a,b)$ with slope $m$ is the graph of the function $f(x) = m(x-a) + b$. Since the slope in a graph of a line is ...
46 views

### Weird question about natural numbers. Obvious or not?

Given any subset $A,C \subset \Bbb{N}$, there exists a maximal subset $B \subset \Bbb{N}$ such that for all $b \in B, a \in A, \ |b - a| \in C$. For instance $A = \{3,5\}$, $C = \{2,4\}$, then ...
112 views

### how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$ For ...
120 views

### Proving $\frac{n^n}{3^n} < n!$ for $n\ge6$ by induction

How would I prove this using mathematical induction: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$. Here is what I have tried: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$ Base case: ...
120 views

### Infinite Chain of Implication Statements - Can it have a Conclusion?

First, does an infinite string of implication statements have a conclusion? If so, is there a such thing as a "closure" of such a beast, giving a conclusion? I am also trying to determine if the ...
280 views
+100

### Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
30 views

### Show that (c,a)=(c,b)

In my book I have the implication: If $gcd(a,b)=1$ and $c|(a+b)$, then $gcd(c,a)=gcd(c,b)=1$. It gives me a hint that begins by supposing that $gcd(a,c)=gcd(b,c)=d$. But in my opinion, I do not ...
### Prove that $B = \bigcup\{A_\alpha \mid \alpha \in[1,2]\}$
I am working this question: Set $B = \{(x, y)\mid 1 \le x^2 + y^2 \le 4\}$, $A_\alpha = \{(x, y)\mid x^2 + y^2 = α^2\}$. Prove that $\bigcup\{A_\alpha\mid \alpha \in [1, 2]\} = B$. because this ...