For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

2
votes
2answers
46 views

There is a best performer in a round robin tournament

At a social bridge party every couple plays every other couple exactly once. Assume there are no ties. If $n$ couples participate, prove that there's best couple in the following sense: A couple ...
0
votes
1answer
55 views

Induction problem prove that at least one of the coefficients Cn is even

For $n \in \mathbb{N}$ regard $1+x+x^2$ as a polynomial, i.e., $$(1+x+x^2)^n = \sum C_n(x^n)$$ with $C_n \in \mathbb{N}$, and prove that at least one of the coefficients $C_n$ is even. I really ...
1
vote
0answers
51 views

How to prove by induction that $(n+1)^n < n^{n+1}$ for $n\ge 3$? [duplicate]

Here is an inequality (let's call it - "$A(n)$") that has to be proved: $$ (n+1)^n < n^{n+1} \text{ for } n\ge3. $$ I'll skip the first two steps of induction and move right to the induction step ...
1
vote
0answers
60 views

Show inequality of recursive defined exponantial function.

Given the following function: $f(1) = 2$ $f(x+1) = 2^{f(x)}$ Show that $f(i) > f(i-1)^{i-1}$. Starting with some $i > i_0$. Intuitively I can easily see why this is so. Basically ...
0
votes
2answers
45 views

Math induction problem. [duplicate]

How to prove the following with induction? $$\sum_{k=1}^{2n} \frac{1}{k(k+1)} = \frac{2n}{2n+1}$$ I have difficulty solving this example. I got past base part where I prove that $L(1) = P(1)$ but I ...
1
vote
3answers
70 views

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer How do I prove the above expression using mathematical induction? So ...
1
vote
1answer
52 views

Why does the conclusion of induction proofs hold even when the base case is greater than $1$?

The principle of mathematical induction states that if $X\subseteq \mathbb{N}$ satisfying $1\in X$ and if $k\in X$ for all $k<n$, then $n\in X$. Then $X=\mathbb{N}$. Now, consider the claim: ...
1
vote
2answers
45 views

Determining a rule for the remainder when $3^n$ is divided by $13$

After some direct calculations, it appears that the powers of $3$ form a cycle of $1$, $3$, and $9$ when divided by consecutive powers of $n$. For example $$3^0 \equiv 1 \pmod{13}, 3^1 \equiv 3 ...
0
votes
2answers
30 views

Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?

I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens. So begin with an intended contradiction: ...
3
votes
1answer
97 views

Double Induction of $x^n < (n^n)(2^x)$

For all real numbers $x, x < 2^x$. Use this fact to show that for any positive integer $n$ : $x^n < (n^n)(2^x)$, for all real numbers $x > 0$. Let f(x,n) be x^n < (n^n)(2^x) then ...
1
vote
1answer
29 views

How to generalize induction from this definition?

Definition: An inductive set $A$ is a one that satisfies: $1\in A$ and $k \in A\implies k+1\in A$. If we characterize the natural numbers as the set which has the following properties: $\Bbb N$ is ...
0
votes
0answers
27 views

Prove by induction the inequality

I tried to solve this but I don't really know how to deal with it. What $n$ should I take for the basis case, as it says take $n$ sufficiently large For $k \in \mathbb{N}$ fixed and $n \in ...
4
votes
1answer
70 views

inequality of two functions

I have the following problem. I need to show that $b(i)>b(i-1)^{i-1}$ for $i>k$ for some $k$. $b$ is the following function: $b(1)=2$ and $b(n)=2^{b(n-1)}$ I tried to do this by induction, but ...
2
votes
3answers
55 views

Induction proofing of a sequence

A sequence $a_n$ is defined by: $a_1=1, a_2 = 1, a_n = a_{n-1} +2*a_{n-2}$ for all n> 2. show that $a_n = 1/3*(-1)^{n-3}+{2^n}/3$ by induction. I'm not quite sure on how to approach this induction ...
1
vote
4answers
50 views

Proof by Induction for Natural Numbers

Show that if the statement $$1 + 2 + 2^{2} + ... + 2^{n - 1} = 2^{n}$$ is assumed to be true for some $n,$ then it can be proved to be true for $n + 1.$ Is the statement true for all $n$? ...
0
votes
1answer
38 views

Proof By Induction for arbitrary integers [closed]

Assume that $|x + y| \leq |x| + |y|$ for all $x,y \in {Z}.$ Use this assumption and induction to prove that $$|a_1 + a_2 + ... + a_n| \leq |a_1| + |a_2| + ... + |a_n|$$ for all integers $n \geq 2$ ...
-5
votes
2answers
41 views

What can the principle of induction prove? [closed]

What theorems can I prove with the principle of induction aside from that every number has a successor and 1+2...n = (n(n+1))/2 ?
1
vote
2answers
37 views

Let $y$ be real, $n$ is natural, and $\varepsilon>0$. For some $\delta>0$, if $u$ is real and $|u-y|<\delta$, then $|u^{n}-y^{n}|<\varepsilon$

I've almost got this problem solved, and I need a(some) pointer(s) as to finishing this problem up (which will be greatly appreciated [!]). Here is the full, problem statement in its exact form. ...
1
vote
2answers
56 views

Use Proof of Induction to prove $\sum_{k=1}^{2n} (-1)^k k = n$

Base Case: \begin{eqnarray*} \sum_{k=1}^{2n} (-1)^k k = n\\ (-1)^1 (1) + (-1)^2(2) &=&1 \\ 1=1 \end{eqnarray*} Inductive Step: For this step we must prove that \begin{eqnarray*} ...
1
vote
3answers
90 views

Induction: $\sum_{k=1}^{2n} (-1)^k k = n$

Use the proof of induction to show : $\sum_{k=1}^{2n} (-1)^k k = n$ I know how to show the base step of this problem, but in showing the inductive step I am having trouble determining how to show ...
0
votes
0answers
34 views

The digital root of factorials from 6! to infinity! is always 9.

While observing digital roots of factorials, i observed that , digital root of (5+n)! where 'n' is any natural number , is always 9. The reason lies in the number 720. It can also be written as ...
0
votes
2answers
30 views

Question about the structure of the proof in how the well-ordering implies induction

I am reading a text, and I have a question regarding the logical structure of the following proof. $(1)$: $1\in X$ and $(2):$ If $k\in X$ for all $k<n$, then $n\in X$. When we prove ...
3
votes
3answers
72 views

Proof by induction on n

So I aim to prove that $n^2 \leq 2^n + 1$ for all integers $n \geq 1$. We can see that this is true for $n=1$ since $1 \leq 3$. Now I suppose that this is true for an arbitrary $k$ such that $k \geq ...
0
votes
3answers
33 views

Need help finding the series in order to prove by induction

I need to prove that for all natural numbers $n$, $\frac{n(n+1)(n+2)}{6}$ is a natural number. The problem is that I can't seem to figure out what the series is, the LHS. Any help would be ...
0
votes
0answers
32 views

prove by induction that T is increasing

I have following recurrence relation, $T(n) = T(\lceil\frac{n}{2}\rceil) + T(\lfloor\frac{n}{2}\rfloor) + f(n)$ with $f(n)\in \Theta(n)$ and the text book says that we can prove by induction that T ...
2
votes
2answers
67 views

Is my induction proof of $2^{n} > 2n+1$ correct?

Hello I am wondering if anyone can conform that the method I use in the following proof is valid. If not please inform me/ point me in the right direction. It is a very basic question, i.e. to prove ...
2
votes
3answers
119 views

Double induction example: $ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + q^n = \frac {q^{n+1}-1}{q-1} $

I'm working on a double induction problem with the following prompt: Prove by induction on $n$ that for any real number $q > 1$ and integer $n \ge 0$: $$ 1 + q + q^2 + q^3 + \cdots + q^{n-1} ...
2
votes
2answers
318 views

Solving recursive formulas, proving with induction

I thought I had the answer to this problem but I seem to be off, something is wrong. The prompt: Find the exact solution to the following recursive formulas. You may guess the solution and then ...
2
votes
1answer
26 views

Prove by induction that the function $a(n)=5a(n-1)-6a(n-2)$ is equal to $2^{n}+3^{n}$ when a(1)=5 and a(2)=13

I'm having a bit of trouble proving this problem, as I'm not sure what to do at a specific step. For the sake of brevity I'm going to skip the base step where you prove that the original case is ...
0
votes
4answers
43 views

Show that 2|n(n+1) using induction [duplicate]

Show that 2|n(n+1) using induction I tried but im stuck , it still (n+1)(n+2) Two successive numbers It's simple using the the methode that n=2k or n=2k+1 Can someone help or give a hint ?
2
votes
2answers
39 views

a problem with the induction hypothesis

I have used mathematical induction in a lot of excercices but I still feel like I am missing something important and that I am only manipulating formulas. Maybe there's also a language issue because ...
4
votes
3answers
475 views

Trapped in Induction, how to get out?

Example 1: Prove by induction that $1+3+5+...+(2n-1)=n^2 \text{ for all } n \in \mathbb{N}....(*)$ Proof: Step 1: For $n=1$, left-side we have $(2(1)-1) = 1$. Right-side we have $(1)^2 = 1$. Step ...
2
votes
4answers
68 views

Prove that $n^{(n+1)} > (n+1)^{n}$ when $n\geq 3$ [closed]

Firstly, for $n=3$, $$3^4 > 4^3$$. Secondly, $(n+1)^{(n+2)} > (n+2)^{(n+1)}$ Now I'm stuck.
2
votes
4answers
60 views

Trying to prove $\sum_{i=1}^{N} i^3 = (\sum_{i=1}^{N} i)^2$

I'm trying to prove $\sum_{i=1}^{N} i^3 = (\sum_{i=1}^{N} i)^2$ but I got stuck along the way. This is what I have so far: The base case is true when $N =1$. Then for the inductive step I did: ...
1
vote
1answer
32 views

Why is strong induction needed here?

I'm currently reading the Wikipedia page proof on the Ballot Theorem, where one of the provided proofs was via induction. They start off with two base cases, one where the first candidate receives ...
1
vote
3answers
82 views

Trying to prove $\sum_{i=1}^{N-2} F_i = F_N -2$

I'm trying to prove that $\sum_{i=1}^{N-2} F_i = F_N -2$. I was able to show the base case for when $N=3$ that it was true. Then for the inductive step I did: Assume $\sum_{i=1}^{N-2} F_i = F_N -2$ ...
6
votes
4answers
559 views

Prove by Induction: $8^n - 3^n$ is divisible by $5$ for all $n \geq 1$

Prove by Induction that for all $n \geq 1$ we have $$8^n - 3^n \text{is divisible by 5} ...(*)$$ My proof so far Step 1: For $n=1$ we have $8^1 - 3^1 = 8 - 3 = 5$ which is divisible by 5. ...
0
votes
1answer
60 views

Proof using induction Σ k+3 = n^2 / 2 + (7/2)n

So I have the following problem ...
2
votes
2answers
54 views

100-level discrete maths, induction problem, prove $n^2 \ge 2n + 1$

I've just run into this problem, and was able to go as far, and understand the induction step up to the bolded section. The last part I found in the back of my book, italicized, I can't understand. ...
1
vote
1answer
39 views

Show that $\sum_{i=1}^{n}[\log_{2}(n/i)]$ is O(n), hint use Stirling's Approximation

Assume that n is a power of 2. Hint 1: Use induction to reduce the problem to that for n/2. Hint 2: Alternative hint -> use Stirling's Approximation. Im trying to solve this problem using the lime ...
0
votes
4answers
31 views

How did the solution to this system of equations get a power of n?

I have been reading up on how to solve problems relating to ideal gases. In a certain example problem in the book, Questions and Problems in school Physics by Tarasov and Tarasova, a system of ...
2
votes
2answers
61 views

Bernoullis inequality proof

Hi I'm asked to do a proof for bernoullis inequality which is $(1+a)^n \geq 1+na$ where $a\geq-1$ I'm proving by induction by the way. So far these are my steps $(1+a)^1 \geq 1+a$ Then $(1+a)^k ...
16
votes
5answers
880 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}$?
1
vote
3answers
57 views

Induction proof.

Homework question, so just a pointer would be nice, for starters. I'm trying to prove $2 \mid 5^{2n} - 3^{2n}$ by induction. I use $n=0$ as the base step, and assume $5^{2n} - 3^{2n} = 2k$ as my ...
0
votes
1answer
31 views

Prove the following using induction on d (matrices)

I manage to reach the step where I need to prove n = k + 1 but I am battling to complete the proof as I am not certain what to do with the exponents in my answer. I will run through the proof as I ...
1
vote
1answer
29 views

Theory of Computation Notation Proof

The Question: Show that if $f(n) = \mathcal{O}(g(n))$ and $g(n) = \mathcal{O}(f(n))$, then $f(n) = \Theta(g(n)).$ I know that since $\Theta$ is a stronger notation than $\mathcal{O}$, then: $f(n) = ...
1
vote
5answers
238 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 ...
0
votes
1answer
24 views

Help with induction question

I'm trying to prove the following equation by induction, but my base case isn't working. for all n>2. For my base case I did n=3, and on the LHS I got 8/9 and the RHS I got 2/3. Helppp.
0
votes
1answer
30 views

Trying to correctly write the proof using *strong* induction of the sum of the nth positive integer

I'm learning about proofs using induction and our professor want us to always use strong induction when giving proofs. In my understanding, strong induction is used to show the range of numbers you ...
0
votes
2answers
97 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...