0
votes
5answers
49 views

Proof of $\forall n \in \Bbb N$, $n > 2 \implies n! < n^n$

What I've got so far is this: Base case: n = 3 then $3 *2 * 1 = 6$ and $3^3 = 27$ $\therefore 6 < 27, 3! < 3^3$ So the base case is true. So if we assume $n! < n^n$ (n > 2) $(n + 1)! = ...
1
vote
0answers
58 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
0
votes
1answer
57 views

am i cheating in this number theory proof?

the question (from burton's elementary number theory); $verify\ that\ \forall n\ge 1,$ $$2\cdot6\cdot10\cdots(4n-2)=\frac{(2n)!}{n!}$$ my work/proof; this is obviously true for $n=1$, so assume ...
0
votes
1answer
39 views

Inductive proof of inequality $a\le ab$ for nonnegative integers

I reading about of proof of the claim "If $a \ge 0$ and $b > 0$, then $a \le ab$. (Here $a$ and $b$ are integers.) The proof the author is employing is inductive. I understand the basis case; ...
-1
votes
1answer
21 views

Inductive Proof Algorithm

so I'm working on an algorithms assignment and am having a tough time understanding what to do: The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$ Right now I have gotten this far: $$T(1) = ...
0
votes
1answer
133 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
2
votes
1answer
28 views

Question on Induction (Very Simple)

I've just started a course in mathematics at university, and our current topic is mathematical induction. I've been given the following question: $$1+4+4^2+....+4^{n-1}=\frac{4^{n}-1}{3}.$$ I get ...
1
vote
1answer
43 views

Check workings for Strong Induction (Proof by Contradiction)

I want to prove the following: Suppose that $P(n)$ is a statement involving a general positive integer $n$. Then $P(n)$ is true for all positive integers $n$ if: i) $P(1)$ is true, and ...
2
votes
1answer
42 views

Generalized Induction Verification

Consider the following simple exercise. Prove or disprove: $\gcd(km, kn) = k \gcd(m, n)$, where $m, n, k$ are natural numbers. Now, this is easy to prove using prime factorization. Knowing that ...
1
vote
1answer
50 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
0
votes
1answer
82 views

How can I prove the correctness of this multiplication algorithm?

I want to know how I can prove that this algorithm is correct: ...
0
votes
3answers
72 views

Prove that $n = 2a + 3b$.

How can I prove by induction that for any natural number $n$ there exists integers $a,b$ so that $2a+3b=n$ I can prove the base case, and I can imagine why it works but how can I prove it ...
2
votes
3answers
56 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
3
votes
1answer
37 views

Where did this “+1” term come from for this inductive proof?

Where did this "+1" term come from for this inductive proof? It is in boxed in black. For context, We are trying to prove this sequence: has the following solution: $$x_{ n }=\frac { 3^{ n+1 ...
6
votes
0answers
68 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
1
vote
2answers
71 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
2
votes
0answers
48 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
17
votes
3answers
712 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
0
votes
0answers
41 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
3
votes
2answers
59 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
1
vote
1answer
27 views

Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$ I used induction beginning successfully with n=0 (or n=1), then making the step to n+1: An x exists so that $13x = 4^{2n+3}+3^{n+3}$ $13x = 16*4^{2n+1}+3*3^{n+2}$ ...
2
votes
3answers
53 views

How can I prove $2^n > n^2 $ by induction using a basis $> 4$ [duplicate]

I've been trying to prove this statement by induction; however, in following the steps I normally take I end up utterly stuck. I know that I must be missing something, but I have been stuck on this ...
1
vote
3answers
29 views

proof by induction - algebra mistake?

I have been working on this proof for a few hours and I can not make it work out. $$\sum_{i=1}^{n}\frac{1}{i(i+1)}=1-\frac{1}{(n+1)}$$ i need to get to $1-\frac{1}{k+2}$ I get as far as ...
3
votes
1answer
166 views

Proof by induction - correct inductive step?

The problem: $$ x_1 \geq x_2 \geq ... \geq x_{3n} \geq x_{3n+1} \geq 0 $$ Show that: $$ x_1^2 - x_2^2 + ... - x_{3n}^2 + x_{3n+1}^2 \geq (x_1 - x_2 + ... - x_{3n} + x_{3n+1})^2 $$ I'm trying to ...
0
votes
1answer
46 views

Tangent equation divisible by (x-y)

I have attempted this proof but I am not sure is the induction step is correct any assistance would be appreciated also I am not sure if i have proved what I was trying to. Let ...
1
vote
2answers
94 views

Using induction, prove that $(-7)^n -9^n$ is divisible by $16$

First of all, I think the problem should be $(-7)^n -9^n$ is divisible by $-16$ because if I test the basis by letting $n=1$, I have $-16$ instead of $16$. Edit: Alright ... I sort of understand why ...
0
votes
0answers
54 views

The Toad and Frog Game - Proof by Inducation

Toads and Frogs is played on a 1 × n strip of squares. At any time, each square is either empty or occupied by a single toad or frog. Although the game may start at any configuration, it is customary ...
3
votes
2answers
205 views

Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is... "Any set $S$ of ...
4
votes
3answers
93 views

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction: How to prove one of them?

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction How to prove one of them ? On Proofwiki there is an article proving the equivalence of the ...
1
vote
2answers
67 views

What is wrong with the proof given below?

This problem comes from Solow's book, 2nd edition. What is wrong with the proof given below? If $r$ is a real number with $|r| \leq 1$, then for all integers $n \geq 1, 1 + r + r^2 + \ldots + ...
2
votes
4answers
111 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
3
votes
4answers
146 views

Is this backwards reasoning?

Yesterday I was answering a question on induction: Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear Basically, I was proving a certain formula using ...
1
vote
1answer
80 views

Is this a correct proof by contradiction?

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction as ...
0
votes
1answer
63 views

Why is this proof by induction incorrect? [closed]

Let $P(n)$ be the statement "$\sum_{i=1}^{n}i=\frac{(n+\frac{1}{2})^2}{2}$". Basis Step: Clearly $P(1)$ is true as the formula holds for $n=1$. Inductive Hypothesis: Suppose that $P(k)$ is true for ...
0
votes
1answer
58 views

Is this horse proof by induction okay? [duplicate]

Let $P(n)$ be the statement "all horses in a set of n horses are of the same colour." Basis Step: Clearly, $P(1)$ is true. Inductive Hypothesis: Suppose that $P(k)$ is true for some arbitrary ...
1
vote
3answers
76 views

Prove by induction that $3\mid (n^3 - n)$

I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure it's correct. My answer: Proof by induction: ...
1
vote
1answer
543 views

Proof by induction Involving Factorials

My "factorial" abilities are a slightly rusty and although I know of a few simplifications such as: $(n+1)\,n! = (n+1)!$, I'm stuck I have to prove by induction that: $$\sum_{i=1}^n\frac{i-1}{i!} = ...
2
votes
2answers
177 views

basic induction probs

Hello guys I have this problem which has been really bugging me. And it goes as follows: Using induction, we want to prove that all human beings have the same hair colour. Let S(n) be the ...
3
votes
2answers
83 views

Prove by induction that $n < 2 ^n $ where $n \in \mathbb{N}$ [duplicate]

Example question in a textbook that I don't understand. Proof works for n = 1 Setting for k makes $k < 2^k $ Setting for k + 1 makes $k+1 < 2^{k+1} $. Here, I would be stuck, the book ...
4
votes
0answers
75 views

Prove that $1^2-2^2+3^2-…+(-1)^{n-1} n^2$=$(-1)^{n-1}\frac{ n(n+1)}{2}$ whenever n is a positive integer using mathematical induction.

I am wondering if the third to last equation is correct, where i factored out the $(-1)^k$. The first term is inside the parenthesis is $(-1)^{-1}$. Is this correct? If I multiply it out again,, wont ...
2
votes
2answers
6k views

Proof by induction: $2^n > n^2$ for all integer $n$ greater than $4$ [duplicate]

I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list: Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than ...
5
votes
3answers
1k views

Strong Induction Proof: Fibonacci number even if and only if 3 divides index

The Fibonacci sequence is defined recursively by $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n−1} + F_{n−2} \; \text{ for } n ≥ 3.$ Prove that $2 \mid F_n \iff 3 \mid n.$ Proof by Strong Induction : ...
0
votes
1answer
918 views

The cardinality of the power set with $N$ elements is equal to $2^N$ [duplicate]

Let $\mathcal{P}(X_N)$ be the power set of a set $X$ with $N$ elements. I am trying to prove by induction that its cardinality $\mid \mathcal{P}(X_N) \mid = 2^N$. Firstly, I think it helps to ...
4
votes
5answers
364 views

Prove that $1^3 + 2^3 + \cdots + n^3 < n^4$.

I am trying to prove the following: $1^3 + 2^3 + \cdots + n^3 < n^4$ if $n \in \mathbb{N}, n>1$ by induction. From there, I am to prove that the sum is $< \frac{n^4}{2}$ if $n>2$. My ...
1
vote
1answer
91 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
5
votes
1answer
284 views

What is wrong with my induction proof?

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ prove that for all $n \ge 1, a_n < ...