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

-1
votes
5answers
112 views

Prove number of handshakes between $n$ people is $\tfrac{n(n−1)}{2}$ by induction [closed]

How do we calculate the number of handshakes between $n$ people? And where do I apply the inductive step?
3
votes
2answers
80 views

Proving that $\sum\limits_{k=0}^{2n}(-1)^k\binom{4n}{2k}=(-4)^n$

I need sum this numerical serie. $\sum\limits_{k=0}^{2n} (-1)^k \begin{pmatrix}4n\\2k\end{pmatrix}$ I know that the result will be $(-4)^n$ but i don't know how can I get it. Could you help me with ...
6
votes
1answer
155 views
+50

Formula for cos(k*x)

I need to prove that: \begin{align} c_k =&\; \cos(k\!\cdot\!x)\\ c_k :=&\; c_{k-1} +d_{k-1}\\ d_k :=&\; 2d_0\!\cdot\!c_k +d_{k−1}\\ d_0 :=&\; −2\!\cdot\!\sin^2{(x/2)}\\ \end{align} ...
1
vote
2answers
42 views

Recursively defined set subset proof

Consider the subset $S$ of the set of integers recursively defined by BASIS STEP: $3 \in S$. RECURSIVE STEP: If $x \in S$ and $y \in S$, then $x+y \in S$. Q: Show that the set $S$ is ...
3
votes
1answer
34 views

On a generalization for $\sum_{d|n}rad(d)\phi(\frac{n}{d})$ and related questions

Let $\phi(m)$ Euler's totient function and $rad(m)$ the multiplicative function defined by $rad(1)=1$ and, for integers $m>1$ by $rad(m)=\prod_{p\mid m}p$ the product of distinct primes dividing ...
1
vote
4answers
85 views

prove that $n(n+1)$ is even using induction

the base case of $n=1$ gives us $2$ which is even. assuming $n=k$ is true, $n=(k+1)$ gives us $ k^2 +2k +k +2$ while $k(k+1) + (k+1)$ gives us $k^2+2k+1$ whats is the next step to prove this by ...
0
votes
1answer
16 views

Structual induction on mirror(mirror t) = t

I have to prove that for all binary trees $t$ the following property holds: $$mirror(mirror(t))=t$$ $mirror(t)$ is defined as: $$mirror(t) =\begin{cases} Empty, & \text{if $t$ is Empty} \\ ...
2
votes
0answers
43 views

Prove: $n\in\mathbb{N}$ is not divisible by $2^n-1$ if $n>1$ [duplicate]

Prove: $n\in\mathbb{N}$ is not divisible by $2^n-1$ if $n>1$ Using induction: For $n=2\Rightarrow 2$ is not divisible by $3$ For $n=k\Rightarrow k$ is not divisible by $2^k-1$ For ...
1
vote
1answer
43 views

$(|x_1|+|x_2|+…+|x_n|)$ vs $\sqrt{(|x_1|^2+|x_2|^2+…+|x_n|^2)}$, which is larger and why?

Actually, I know which is larger. Is there some kind of rule that states that the square root is less or equal to the first expression? ** My tag is probably incorrect **
0
votes
1answer
19 views

Binomial Theorem proof using Cauchy Induction

By differentiating the nth binomial expansion, it is possible to deduce the (n-1)th expansion is true. Is it possible to then show that the nth expansion implies the k*nth expansion for some positive ...
-2
votes
2answers
37 views

Prove by induction that $\sum_{i=1}^n i \geq \frac{n^2}{2}$ [closed]

Can someone show me a formal proof of this exercise ? \begin{equation} \sum\limits_{i=1}^n i \geq \frac{n^2}{2}, \quad \forall n \in \mathbb{N}. \end{equation} Thanks to anyone who can help! :)
0
votes
2answers
193 views

Is it possible to prove by induction that $1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{n^2}<2\space\space \forall n\geqslant 1?$ [closed]

Let's denote the inequality in question by $A(n)$. I am looking for the way to prove this inequality using "direct induction" (see my question 1 below). By usual induction I mean ...
3
votes
1answer
57 views

Square of a sum equals sum of cubes

Consider a sequence $(a_n)$ of positive numbers such that $$(a_1+\cdots+a_n)^2=a_1^3+\cdots +a_n^3,\quad n\ge 1.$$ Prove that $a_n=n$ for all $n\ge 1$.
0
votes
1answer
102 views

Prime Factorization and Induction

I have a discrete math problem and I need some guidance on where to start: Let $ n \geq 2$ and let $n = p_1p_2...p_k$ be its prime factorization, where the primes are not necessarily distinct. Prove ...
3
votes
1answer
36 views

Proof that max value of $n$-bit binary number is $2^n - 1$

After reading this programming question , I wanted to prove the assertion. I'm wondering whether the below would be considered a complete and clear proof. Claim: $\sum_{i=0}^{n-1} 2^i = 2^n - 1.$ ...
0
votes
2answers
45 views

Is induction defined on natural numbers?

Whenever I use the inductive method to prove some questions, I usually start from the $n=1$ case and assume it holds for all $n$. However, is the reason why we do not consider the $n=0$ case because ...
0
votes
2answers
47 views

Prove with induction that $a_n = 2^n-1$

I have $a_2=3, a_3=7, a_4=15$ and $a_n = 1+2a_{(n-1)}$ how do I use proof by induction to prove that $a_n = 2^n -1 ?$ I'm aware of the steps with showing that its true for $n=1$ and assuming true ...
1
vote
2answers
71 views

A possible error in the inductive proof of $2k+1<2^k$ for $k\ge 3$

This is the answer to a basic induction problem. I feel that that the author may have made a typo... $2^k + 2^k = 2^k \cdot 2^1 = 2^{k+1}$
3
votes
1answer
38 views

A recursive definition

I have this problem: Q4 of this Prove by induction that no matter how the dots are coloured red and blue, it is possible to have a successful trip around the circle if you start at the correct ...
0
votes
1answer
46 views

Prove $\frac n2 > \sum_{k=1}^n (1/k) -1$

This is the problem: $$ \frac n2 > \sum_{k=1}^n (1/k) -1$$ Here's my try. P(1): $$\frac12 > \frac11 -1$$ $$\frac12 > 0$$ P(n) => P(n+1): $$\sum_{k=1}^{n+1} \frac1k - 1 = \sum_{k=1}^n ...
0
votes
3answers
47 views

Induction on powers

If $n \geq 3$, prove that $3^n \geq n^3$. Progress. I tried using induction and saying assume $3^k \geq k^3$. Then I got $3^{k+1} = 3^k \cdot 3 \geq 3k^3$. Now I am stuck.
3
votes
1answer
35 views

The sum of binomial coefficients $\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}$

Prove by induction: $$\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}$$ I already know that: $$\sum_{i=1}^n \binom{i}{2} = {i+1 \choose 2+1}$$ And the LHS is now equal: $$\sum_{i=1}^n \binom{i}{2} + ...
-1
votes
2answers
53 views

proving that if $x^2 + x + 1$ is even, then $x$ is odd by induction

Let $x$ be an integer. If $x^2 + x + 1$ is even, then $x$ is odd. To prove this, I prove its contrapositive. If $x$ is even, $x^2 + x + 1$ is odd. All even numbers can be shown as $2k$ and all odd ...
0
votes
1answer
34 views

which is the best proof to use for gcd(a, b) = gcd(a, b − a)

Prove that gcd(a, b) = gcd(a, b − a) What is the best way to prove this? using induction? or does there exist a more efficient method?
2
votes
2answers
80 views

Prove by induction $ \sin x + \sin 2x + … + \sin nx = \frac {\sin (\frac {n + 1} {2} x)} {\sin \frac{x}{2}} \sin \frac{nx}{2} $

Prove by induction $$ \sin x + \sin 2x + ... + \sin nx = \frac {\sin (\frac {n + 1} {2} x)} {\sin \frac{x}{2}} \sin \frac{nx}{2} $$ What I have for now: $$ \frac {\sin (\frac {n + 1} {2} x)} ...
1
vote
2answers
41 views

Induction: Every connected graph has a spanning tree

Definition A spanning tree of a graph $G$ is a tree $T\subseteq G$, with $V_T=V_G$ Question Proof, by induction, that every connected graph $G$ with $n$ vertices contains a spanning tree. ...
-1
votes
1answer
47 views

Prove that $\frac {(2n)!} {(n!)^2} > \frac{4^n}{n + 1} $

Using mathematical induction prove that: $$\frac {(2n)!} {(n!)^2} > \frac{4^n}{n + 1} $$ I tried to use $n + 1$: $$ \frac {(2(n + 1))!} {((n + 1)!)^2} > \frac{4^{n + 1}}{n + 2} $$ But ...
1
vote
1answer
31 views

Mathematical induction with two nested sums

$\sum_{j=1}^{n} {(2j-1)}{\left(\sum_{m=j}^{n} \frac{1}{m}\right)} = \frac{n(n+1)}{2}$ Would anyone show how to prove this by induction?
5
votes
2answers
32 views

Prove $ \sum_{k=0}^n k4^k = \frac 49((3n-1)4^n + 1) $ by induction

Prove that for every position integer $n$ that $$ \sum_{k=0}^n k4^k = \frac 49((3n-1)4^n + 1) $$ Proof: Let $P(n)$ denote the above statement. Base case: $n=1$ : Note that $$ \sum_{k=1}^1 k4^k = ...
0
votes
0answers
11 views

Robin round all top players

In a certain tournament, where each player plays against other players exactly one time,without ties as a top player is defined a player, who for every other player x, either beats player x, or player ...
0
votes
0answers
16 views

Not understanding how to find a particular solution for non-homogeneous recurrence

I am having alot of trouble trying to follow my textbook when they explain how to find a particular solution. I have posted the section from the book. I am not understanding what the authors mean when ...
0
votes
4answers
33 views

Prove using congruences that $ 7\mid\left(5^{2n}+3\cdot 2^{5n-2}\right)$ , $n \ge 1$

Prove using congruences that: $$ 7\mid\left(5^{2n}+3\cdot2^{5n-2}\right)$$ (is divisible by 7) So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ but i cant prove ...
0
votes
4answers
52 views

inductive step confusion in sum of all positive integers example

I am confused with the inductive step of this very basic induction example in the book Discrete Mathematics and Its Applications: $$1 + 2+· · ·+k = k(k + 1) / 2$$ When we apply $k+1$, the equation ...
0
votes
0answers
16 views

Proving a recurrence's $\Theta$ with induction

Prove with induction that $T(n)=T(\frac n 2)+\log n = \Theta (n^2)$ Starting with the big $O$, the basis $T(2)\le c 2^2$ is obvious. Assume it's true for $n$ and prove for $n+1$: $T(n)=T(\frac n ...
1
vote
1answer
55 views

Prove n! < (n/2)^n by induction

Im supposed to prove that $n! \leq (\frac{n}{2})^n$ by induction and I got to know that its only valid for $ 6 \leq n$. I tried it solving this way: $6! \leq 3^6$ $720! \leq 729$ $(n+1)! \leq ...
2
votes
1answer
36 views

Logical Dependence of Induction on the Well-Ordering Principle

I know from a Discrete Mathematics class in the spring that Mathematical Induction depends on the well-ordering principle for natural numbers. The explanation in my textbook (Rosen) did not give me ...
0
votes
2answers
54 views

Prove by induction $\sum_{i=m}^{n} a_i = \sum_{j=m+k}^{n+k} a_{j-k}$?

I had asked the same question here http://matheducators.stackexchange.com/questions/9999/which-concept-did-i-overlook-in-trying-to-prove-a-property-of-finite-series-sum but it was suggested as ...
1
vote
0answers
20 views

Inductive proof of associativity of free groups

I'm really struggling with the inductive proof of the associativity of free groups, given about halfway down page 6 of this pdf. The bit I'm not getting is this: Suppose now that bc involves a ...
1
vote
3answers
64 views

Show that for any $a\in\mathbb{Z}$, $3 \mid(a^3 - a)$

Show that for any $a\in\mathbb{Z}$, $3 \mid (a^3 - a)$ my solution is : if $a$ is a multiple of $3$ then $a^3-a$ is a multiple of $3$; if $\gcd(a,3)=1$ then by FLT $a^2\equiv 1 \pmod3$, hence $a^3-a ...
2
votes
1answer
24 views

What does it mean when a number 'y' is pseudoprime to base 'x'

I am self learner so I don't really understand about pseudoprime to base 'x' for example) 91 is a pseudoprime to base 3 then is 91 also a pseudoprime to base 2? thank you please explain. ...
2
votes
1answer
32 views

Proof that any $\,a \ge 20\,$ can be written as $\,a = 5b + 6c\,$ where $\,a,\, b\,$ and $\,c \,$ are Natural Numbers

I'm currently working on a problem for an assignment, so forgive me if my question is a little clumsy or vague. I'm trying to get myself headed in the right direction and offer a meaningful question ...
0
votes
0answers
19 views

Is this product of two product factorizations correct?

I am working on an induction proof and would like to know whether this product equality is true: $$\big (\prod_{i=2}^n (\lambda_i-\lambda_1) \prod_{n\ge i > j \ge 1}(\lambda_i - \lambda_j)\big )$$ ...
1
vote
2answers
28 views

Proving L(G) = L using induction and deriving a schema

Consider the following grammar G: S -> aS -> aTb -> a T -> aTb -> a How would I prove that ...
0
votes
1answer
31 views

How to show that $f_{0}f_{1}+f_{1}f_{2}+…+f_{2n-1}f_{2n} = f^{2}_{2n}$

The following problem: The Fibonacci number is denoted by $f_{n}$, show that the following holds when $n$ is a positive integer: $f_{0}f_{1}+f_{1}f_{2}+...+f_{2n-1}f_{2n} = f^{2}_{2n}$ My idea was ...
2
votes
2answers
47 views

Find a formula for $f(n)$ and prove it by induction

The following Problem: «Find a formula for $f(n)$ and prove it by induction» $f(0) = 0$ and $f(n) = f(n-1) -1$ $f(0) = 0$ and $f(1) = 1$ and $f(n) = 2*f(n-2)$ For the first one I thought of $f(n) ...
0
votes
2answers
26 views

Is my process of proving inequalities using Mathematical Induction correct?

$$ 2^n<(n+1)! \quad \text{for all integers} \quad n \ge 2$$ Base Case: $$ 2^2< (2+1)! = 4< 6 $$ Correct Assumption: $$ P(k): 2^k<(k+1)!$$ $$P(k+1)= 2^{k+1}<(k+2)!$$ Now we start ...
3
votes
3answers
30 views

Every nonempty subset of the natural numbers has a least number

Proposition: Every nonempty subset $A$ of $\mathbb{N}$ has a least element. We assume the opposite: $$\exists \left( A \subseteq \mathbb{N} \wedge A \neq \varnothing \right): \forall s \in A: ...
3
votes
7answers
125 views

Prove that $5$ divides $3^{3n+1}+2^{n+1}$

Prove that $5$ divides $3^{3n+1}+2^{n+1}$ I tried to prove the result by induction but I couldn't. The result is true for $n=1$. Suppose that the result is true for $n$ i.e ...
4
votes
4answers
143 views

Proof that $ n^{n} \leq {(n+1)}^{n} $

I know this seems trivial, but how could I proof this? Should I use Induction? Where $n$ is an integer.
2
votes
2answers
31 views

Sum of Squares for Odd Fibonacci Numbers

I am trying to prove the following theorem by induction: THEOREM: For the Fibonacci sequence $F_1$, $F_2$, ... , $F_n$ defined as, $F_1$ = $F_2$ = 1 $F_n$ = $F_{n-1}$ + $F_{n-2}$ for n >= 3, For ...