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

0
votes
2answers
52 views

Need help ordering a list of functions

List the functions below from lowest order to highest order. If any two or more are of the same order, indicate which. $n$, $n^3$, $2^n$, $\ln n$, $n^2$, $\ln^2 n$, $\sqrt n$, $2^{n−1}$, $\ln n$, ...
2
votes
2answers
1k views

Understanding mathematical induction for divisibility

I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it ...
0
votes
3answers
75 views

Prove by induction that… $1+3+5+7+…+(2n+1)=(n+1)^2$ for every $n \in \mathbb N$

I'm not too sure exactly how to approach this question. Would anyone be able to give me any helpful advice or some sort of direction? I have a little problem with induction. Prove by induction that: ...
0
votes
1answer
45 views

A question about numbers with a certain property

Find (if exists) a subset of the non negative integers $X$ such that for every non negative integer $n \in \mathbb{N}\cup\{0\}$ there is exactly one solution of the form $a+2b=n$ with $a,b \in X$ I ...
0
votes
0answers
23 views

I need to prove by induction $(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$ [duplicate]

Prove by induction $$(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$$ I can check the cases $n=1,2,3$ but I don't know how the prove the general case. Thank you very much! ...
1
vote
1answer
72 views

Prove by induction $\sqrt{1}+\sqrt{2}+\sqrt{3}+…+\sqrt{n}\ge\frac{2}{3}n\sqrt{n}$ for all positive integers

Assumption: $\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{k}\ge\frac{2}{3}k\sqrt{k}$ Prove true for $n=k+1$ $$\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{k}+\sqrt{k+1}\ge\frac{2}{3}(k+1)\sqrt{k+1}$$ I'm upto ...
0
votes
2answers
60 views

Proof my by mathematical induction $\sum_{i=1}^{n} \frac{(-1)^{i-1}}{i} > 0 $

I proved it true for the base case but have no idea how to implement the assumption that it's true for n=k when trying to prove for n=k+1. Am i right in saying there would be two cases i.e. k is odd ...
0
votes
0answers
14 views

Help with Induction Proof of Gradient Descent Update

Below is a snippet from a paper describing a technique for taking account of importance weights ($h$) in online gradient descent, using the scaling factor $s(h)$ instead of multiplying the gradient by ...
0
votes
3answers
46 views

Induction question?

I have a problem that is supposed to use induction, but I have no idea how to solve it. Could I get some help? The closed form sum of 12 $\left[ 1^2 \cdot 2 + 2^2 \cdot 3 + \ldots + n^2 (n+1) ...
0
votes
1answer
32 views

conjecture and prove set induction problem

Let $X_n$ = $\{1,2,3,4,\ldots,n\}$ (a set). Conjecture and prove that $\sum_{\emptyset \neq A\subseteq X_n}\frac{1}{p_A}=n$, where $p_A$ is the product of the subset. Attempt: $\sum_{\emptyset \neq ...
0
votes
1answer
65 views

Let n be an arbitrary natural number and let the property P(n) be the equation 2 · 6 · 10 · 14 · … · (4n - 2) = (2n)! / n!

Here's my proof: Base Case: Show that P(1) is true: n = 1 (4(1) - 2) = (2(1))! / (1)! 4 - 2 = 2! / 1 2 = 2 The base case holds. Induction Step: Show that for all natural numbers k, if P(k) is ...
1
vote
1answer
55 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
2
votes
1answer
125 views

Integration by parts, proving inductive case

${1\over2}\int_{-\pi/2}^{\pi/2}cos^{2n-1}(x) dx$ Inductive step: Show that the $integral={(2n-2)(2n-4)...\over (2n-1)(2n-3)...}$ for $n\ge2$ $T(n+1)$=... Attempted int. by parts using ...
2
votes
2answers
346 views

How to prove the binomial coefficient identity $\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$ by induction?

$$\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$$ How can I prove using induction for all values of $n$ and $c$? I have no idea how to start it. Please help!
1
vote
1answer
42 views

Induction proof of the area of a square

English is not my first language, so I'm sorry if I'm not very clear. I can clarify any question you have. Also, I don't know how to use that math formatting so I apologize for it. So I was asked to ...
0
votes
3answers
31 views

Solving a question by mathematical induction [duplicate]

Question : Prove that $$ \sum_{k=1}^n\frac{1}{\sqrt{k}}\le 2\sqrt{n}-1 $$ for all positive integers $n$. I've been thinking a solution for this question for hours but still can't solve it.
1
vote
7answers
97 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...
0
votes
1answer
26 views

Proving order of magnitude

Generally how much proof must be given to prove a statement of order-of-magnitude? for example: $n^2 + 2 log (n) = O(n^2)$ $2 log (n)$ has a lower order of magnitude than $n^2$ so it can be argued ...
1
vote
2answers
57 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
3
votes
1answer
138 views

Euler proof of the formula involving factorial?

Let me be formal and write the formula Euler's Formula: Let $a$ and $n$ be nonnegative integers with $a\geq n.$ Then $$n!=a^n-\binom{n}{1}(a-1)^n+\binom{n}{2}(a-2)^n-\binom{n}{3}(a-3)^n+ > ...
0
votes
2answers
70 views

Using induction to prove a formula for $\sin x+\sin 3x+\dots+\sin (2n-1)x$

I'm working from the text "Intro To Real Analysis" by William Trench. Here is what I have thus far. I will prove using Mathematical Induction that $\sin x+\sin 3x+...+\sin (2n-1)x=\frac{1-\cos ...
0
votes
0answers
23 views

Sum of convolution of divisor function [duplicate]

For every integer $k$ let $d_k: \mathbb{N} \rightarrow \mathbb{C}$ be defined recursively as $d_0 = \mathbf{1}$, $d_k = d_{k-1} * \mathbf{1}$. So for example $d_1 (n) = d (n) = \sum_{d \vert n} 1$ is ...
2
votes
1answer
42 views

Recursive definition of multiplication

I have the following function: $$ \begin{cases} mul (a, 0) = 0&\mbox{if }n=0\\ mul (a, n) = mul (2a, \frac{n}{2})&\mbox{if }n\mbox{ is even}\\ mul (a, n) = mul (2a, \frac{n-1}{2}) + ...
0
votes
0answers
49 views

Proof using induction on sequences

Here's a theorem I'd like to prove using weak induction: Theorem 1: The sequence $\{x_n\}$ is recursively defined as follows: $$x_n=\cos(x_{n-1}) \sin(x_{n-2}) \text{ for } n \geq 2$$ where $x_0 = ...
0
votes
1answer
91 views

conjecture formula/prove by induction

Conjecture formula from following equations, and prove conjecture: $1=1,\\2+3+4=1+8,\\5+6+7+8+9=8+27,\\10+11+12+13+14+15+16=27+64\\$ $S(n)=\sum_{i=(n-1)^2+1}^{n^2}i=(n-1)^3+n^3$ ...
0
votes
1answer
41 views

Mathematical Induction

The sequence of real numbers $a_1$, $a_2$, $a_3$...is such that $a_1$ $=$ $1$ and $a_{n+1} = (a_n + \frac{1}{a_n} )^{\lambda}$ ,where $\lambda$ is a constant greater than 1. Prove by mathematical ...
0
votes
0answers
73 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
1
vote
1answer
39 views

Series Induction problem set:

For all $n$ belonging to $\mathbb N$, let $A_n$ be the number of subsets of $\{1,2,\ldots,n\}$ that do not contain any two consecutive members (including $\emptyset$); (a) Show that $A_n$ is the ...
0
votes
2answers
73 views

prove by induction, not for natural numbers this time, but for real numbers

Prove by induction: suppose there's a vertical column, infinitely tall from the ground. from 0 inches to 2 inches are dangerous zone, and up from 2 inches are safe zone. If you care climbing this ...
4
votes
2answers
330 views

Proof by induction: $\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$

How can the following be proved by induction? $$\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$$ I am out of ideas after practicing for a ...
3
votes
1answer
95 views

How to prove $\sum\limits_{i=0}^{n-1}\frac{i}{2^i} = 2 - \frac{n + 1}{2^{n-1}}$ by induction?

I'm practicing mathematical induction for a discrete math exam. The concept of proving by induction by proving that closedForm(n-1) + sumEquation(n) = closedForm(n) ...
3
votes
0answers
55 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
0
votes
3answers
78 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
2
votes
1answer
47 views

If $a_n=n^\frac 1n-1, n \in \mathbb N$ prove that $0 \le a_n \le \sqrt {2/n}$?

If $a_n=n^{\frac{1}{n}}-1$, $n\in\mathbb{N}$, prove that $0\le a_n\le\sqrt{\frac{2}{n}}$. I tried with induction and signs, got nowhere. Any help is appreciated.
1
vote
4answers
74 views

Prove that the power set of S contains $|2^n|$ elements

From the above explanation, I don't understand why the set that contains {a} will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$ The construction of a new set $S$ is the union of ...
1
vote
3answers
65 views

Prove a sum formula by induction

I am to prove through induction that $$\sum_{k=1}^n (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$ And well, my method seems to be working, but I get stuck when I'm nearly done. First I prove the formula work ...
0
votes
1answer
39 views
0
votes
1answer
48 views
2
votes
3answers
97 views

Prove or Disprove n! = BigOh(2^n) via mathematical induction.

My computer science professor has us tasked with proving or disproving the statement the n! = BigOh(2^n). We are then suppose to say if it's always true, always false, or non-conclusive, ...
0
votes
1answer
29 views

Can someone help me complete this easy proof by induction

$P(n): for -1<x => (1+x)^n >= (1+nx)$ $P(1): (1+x) >= (1+x)$ $P(n+1): (1+x)^{(n+1)} = (1+x)^n*(1+x) ....$ where to go from here?
3
votes
2answers
185 views

Can someone please explain the axiom of induction in lay term?

Axiom of Induction To me, it says, for all P such that P(0) AND for all k is an element of natural numbers P(k) implies P(K+1) implies for all n is am element in the natural numbers of P(n) But ...
5
votes
1answer
122 views

Nested Radicals Induction

How can I show that $\sqrt[2]{2+\sqrt[3]{3+\sqrt[4]{4+\cdots}}} $ (repeated $n$ times) is irrational using induction? I know the base case for $n=1$ looks like: $\sqrt[2]{2}$ is irrational. I also ...
0
votes
2answers
66 views

Sum of the first $n$ numbers that is neither divisible by 2 nor 3.

Show that the sum of the first $n$ positive integers that are divisible by neither 2 nor 3 is $\frac{3}{2}n^2-\frac{1}{2}$ if $n$ is odd and is $\frac{3}{2}n^2$ if $n$ is even. I have verified that ...
2
votes
2answers
120 views

coin problem with two coins, inductive proof

Adjustment This proof is flawed. I want to ask something about the coin problem with two coins. Let $a,b$ be to numbers in $\mathbb{N} \setminus \{0\}$ (elsewhere I include zero) which have no prime ...
1
vote
2answers
43 views

Induction for recurrence

I'm trying to understand an induction proof that aims to prove some function is in $O(n\log{ n})$. It's on page 5 of this PDF: https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf ...
16
votes
6answers
963 views

What are some examples of induction where the base case is difficult but the inductive step is trivial?

According to Wikipedia: ...proofs by mathematical induction have two parts: the "base case" that shows that the theorem is true for a particular initial value such as n = 0 or n = 1 and ...
3
votes
5answers
447 views

proof by induction - explanation on it

Proof by induction. It's pretty useful, and the purpose of it makes a lot of sense. However one thing has always bothered me concerning it. So when you apply induction, one has a base case where you ...
0
votes
0answers
64 views

Induction — n to n+1 [duplicate]

I'm trying to understand an induction proof that aims to prove some function is in $O(n\log{ n})$. It's on page 5 of this PDF: https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf ...
0
votes
2answers
45 views

prove that the sum to n terms of the sequence is $n(n+1)/2(2n+1)$ [duplicate]

Prove that the sum to n terms of the Sequence: $1^2/(1×3),2^2/(3×5),3^2/(5×7),...$ is $ n(n+1)/2(2n+1).$ Im having trouble with this question, firstly ive begun by stating that p(n) denotes the ...
1
vote
1answer
271 views

Induction Proof: Round Robin

In a round-robin tournament, each team plays every other team exactly once. Show that if no games end in ties, then no matter what the outcomes of the games, there will be some way to number the teams ...