Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

0
votes
1answer
94 views

Algorithms - Induction (packing cups into boxes)

I need some assistance on this question. I honestly just have no idea where to go with this one. Question: We have $n\cdot k$ cups. Each of these cups has one of the $k$ different colors. Assume $k$ ...
-1
votes
2answers
24 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
949 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
58 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
42 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
1answer
58 views

Prove if n<m there is at least one [(n/m)]?

If there is n persons and m places to seat. Is it right that at least one seat which contain [(n/m)] persons? Note: I was not able to find the right sign [ is returning first upper integer in case of ...
0
votes
0answers
22 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! ...
0
votes
0answers
23 views

strong induction proof of sequence

Posting even though correct just for feedback, etc. $n_0,n_1$ are lower/upper bounds of true values for strong induction. Guess I could have used different values, like 2 and 3, or 1 and 2, but it ...
1
vote
1answer
49 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
47 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 ...
2
votes
1answer
76 views

A question about how to express a fraction as ${1\over q_1}+{1\over q_2}+ \cdots+{1\over q_N}$

Let $x$ be a positive rational number, strictly between $0$ and $1$. Prove that there is a finite strictly increasing list of positive integers $2 \leq q_1<q_2<\cdots<q_N $ such that ...
0
votes
2answers
43 views

Proof by induction

Prove $n^2 < n!$. This is what I have gotten so far basis step: $p(4)$ is true Inductive Hypothesis assume $p(k)$ true for $k \ge 4$ Inductive Step $p(k+1)$ : $(k+1)^2 < (k+1)!$ $$(k+1)^2 ...
0
votes
0answers
6 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
39 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
25 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 ...
1
vote
1answer
37 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
1answer
13 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 ...
0
votes
1answer
35 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}, ...
1
vote
1answer
44 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 ...
1
vote
2answers
297 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
28 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
28 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
80 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
14 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
37 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$. ...
2
votes
1answer
88 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+ > ...
1
vote
2answers
50 views

Lucas Numbers Proof $L_n = \alpha^n + \beta^n$

Proof by Induction: Lucas numbers are recursively defined as: $L_n = L_{n-1} + L_{n-2}$ where $L_1 = 1$ and $ L_2 = 3 $for $n \ge 3$ Show that: $L_n = \alpha^n + \beta^n$ for $\alpha = ...
0
votes
2answers
53 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 ...
1
vote
4answers
64 views

Proving $4^n > n^4$ holds for $n\geq 5$ via induction.

I know that it holds for $n=5$, so the first step is done. For the second step, my IH is: $4^n > n^4$, and I must show that $4^{n+1} > (n+1)^4$. I did as follows: $4^{n+1} = 4*4^n > 4n^4$, ...
0
votes
0answers
16 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
35 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}) + ...
4
votes
5answers
314 views

Proof by induction involving inequalities

Problem: If $n$ is a natural number and $n\geq4$, then $3^n \geq 2n^2 + 3n$. (Prove by Induction.) Attempt at solution: 1) Given: $n$ is a natural number, $n \geq 4$. 2) Let $P(n)$ be the statement ...
0
votes
0answers
28 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
26 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
32 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
67 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
32 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
67 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 ...
3
votes
2answers
311 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
80 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
26 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
50 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
29 views

Probability and Induction help [closed]

Let $Y=X_1+X_2+ \cdots+X_n$ where $X_1, X_2, \ldots, X_n$ are independent Bernoulli random variables, each with probability of success equal to $q$. Use induction to prove that $Y$ has a Binomial ...
2
votes
1answer
43 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
40 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
38 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
33 views
0
votes
1answer
30 views

Formula for the floor of $n/2$, to be proved by induction

How do you compute this when the base case is all wrong?
2
votes
3answers
49 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
19 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?