1
vote
2answers
53 views

How to simplify the formula for $n$th Fibonacci number when $n=2$?

When n is equal to 2 how do I simplify when the $n=2$ is put into the equation below (by the way I have to prove this formula by induction that when n= any number it will equal that number) ...
2
votes
1answer
17 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
0
votes
2answers
70 views

Mathematical Induction Problem with Fraction

$$(3n-2)^2=\frac{n(6n^2-3n-1)}{2}$$ I can't seem to solve it out to the point where I can prove it right or wrong. I always hit some sort of roadblock where I don't have enough info to prove it ...
0
votes
1answer
73 views

Spivak Chapter 2 Question 1 (i)

I don't understand Spivak's proof by induction of this exercise: Prove by induction $$1^2 + \ldots + n^2 = {n(n+1)(2n+1))\over 6}$$ It's true for $n = 1$ Then the proof continues adding $(k+1)^2$ ...
0
votes
1answer
25 views

Analysis, prove a period by induction

Given that $F(x) = F(x+T)$ is $T$-periodic, prove by induction that $F(x) = F(x+nT)$ for all $n \in \mathbb N$. Would appreciate some help with this... one of my finals practice questions. Thanks.
1
vote
2answers
143 views

Finding a proof to the 'squares' problem

I am trying to find a proof for the general case of the solution to the 'Squares' Problem. This is what I have managed to figure out: If n is the number of squares in the top row, then the number ...
0
votes
5answers
85 views

Use induction to show that $3^n >n^3$ for $n≥4$

Use induction to show that $3^n >n^3$ for $n≥4$. (Note that you have to start at $n=4$ as the result isn't true for $n=3$ !) I am very new to using induction, but as I understand it I have ...
0
votes
3answers
51 views

Prove by mathematical induction for every natural number n. $5+25+125+\cdots+5^n=5/4(5^n-1)$

There's one thing I don't understand. In the work shown for this problem in the image below, why is it adding $5^{k+1}$ to both sides? http://imgur.com/d369K5Y (Part 1) http://imgur.com/X9Q6aTi ...
0
votes
1answer
48 views

Use the principle of mathematical induction to show that the given statement is true for all natural numbers n.

Use the principle of mathematical induction to show that the given statement is true for all natural numbers n. $S_n: 11+23+35+...+(12n-1)=n(6n+5)$ My work: $S_1:(12*1-1) \overset?= 1(6*1+5)$ $11 ...
1
vote
1answer
114 views

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction. $n = 1$: $\sum^{(1)-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac ...
1
vote
0answers
48 views

Proof by induction for all positive integers

$\sum_{j=1}^n j^2 = \frac{n(n+1)(2n + 1)}{6}$ So I did the obvious and plugged one to show that $1^2 = \frac{1(1+1)(2(1) + 1)}{6}$ Now I am trying to show that $1^2 + 2^2 + ... + n^2 + (n + 1)^2 = ...
2
votes
4answers
134 views

prove by induction: $3 + 5 + 7 + … + (2n+1) = n(n+2)$

Use the principle of mathematical induction to prove that $$3 + 5 + 7 + ... + (2n+1) = n(n+2)$$ for all n in $\mathbb N$. I have a problem with induction. If anyone can give me a little insight ...
0
votes
2answers
52 views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a ...
1
vote
2answers
81 views

proof by maths induction

not sure how to prove this: for all positive intergers prove: \begin{equation} 1+2(2)+3(2^2)+...+n(2^{n-1})=(n-1)(2^n)+1 \end{equation} heres my try: prove $n=1$ : \begin{equation} 1=1 ...
1
vote
2answers
51 views

How can I come up with a formula for this summation?

I have to come up with a formula for: $$\sum_{0\le i\le n\text{, i is even}}^\ i^2$$ and then prove it by using induction. I know how to do the proof, but I am stuck on coming up with the formula. I ...
1
vote
2answers
83 views

How do I go about algebraic manipulation of polynomials with many terms?

I'm doing an inductive proof for a homework problem, and for one step, I need to show that $$ \dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30} + (n+1)^4 = \\ ...
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 $ ...
2
votes
2answers
179 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
0
votes
1answer
32 views

Suppose $a_{i}+1=a_{i}q, \forall i \in \mathbb N$, show by induction that if $ q\neq1$, $a_{1}+…+a_{n}=\dfrac{a_{n+1}-a_{1}}{q-1}$

Suppose $a_{i}+1=a_{i}q, \forall i \in \mathbb N$, show by induction that if $ q\neq1$, $a_{1}+...+a_{n}=\dfrac{a_{n+1}-a_{1}}{q-1}, \forall n \in \mathbb N$ Let $P(n)$ be the proposition we want to ...
0
votes
3answers
59 views

Prove by induction that for $q\neq1$, we have $1+q+…+q^{n-1}=\dfrac{q^{n}-1}{q-1}, \forall n\in \mathbb N $

Prove by induction that for $q\neq1$, we have $1+q+...+q^{n-1}=\dfrac{q^{n}-1}{q-1}, \forall n\in \mathbb N $ Let $P(n)$ be the proposition we want to prove. For $P(1)$ we have: ...
0
votes
1answer
74 views

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction [duplicate]

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction
0
votes
2answers
68 views

How $x^2$ increases by $x+1/x$? [duplicate]

I was going through one of the topic "Introduction to Formal proof". In one example while explaining "Hypothesis" and "conclusion" got confused. The example is as follows: If $x\geq4$, then $2^x ...
1
vote
1answer
86 views

7) Prove that $2n-3 \leq 2^{n-2}$ for all $n \geq 5$ by mathematical induction [duplicate]

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$
0
votes
2answers
53 views

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ Thank you for the Review.
1
vote
2answers
41 views

algebra help in AoCP intro to induction

In the introduction of mathematical induction, section 1.2.1 of Knuth's Art of Computer Programming, I'm struggling with (4) especially this relation: $\phi^{n-2} +\phi^{n-1} = \phi^{n-2}(1+\phi)$ ...
0
votes
0answers
43 views

Proof that $ k^2<2^k$ [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $k\geq 5$, prove that $k^2<2^k$. I assumed that $k^2<2^k$ I want to show that $(k+1)^2<2^{k+1}$ The ...
2
votes
6answers
124 views

Proof that $n^3-n$ is a multiple of $3$. [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $n$, prove that $n^3-n$ is a multiple of $3$. I assumed that $k^3-k=3r$ I want to ...
4
votes
2answers
200 views

What is a good example to show high school students why a proof for induction is a reasonable kind of proof?

I teach average-level high school students who have not had much beyond Algebra 1. I want to show them why induction makes sense. I want the sort of problem where it is intuitive that a statement is ...
3
votes
2answers
70 views

Proving by induction that $\sum_{i=2}^n(i^2-i) = \frac{n(n^2-1)}{3}$ for all $n \ge 2$

Doing proof by induction exercises, everything was fine until I tried to do one with $\sum$ : Prove that $$\sum_{i=2}^n(i^2-i) = \frac{n(n^2-1)}{3}$$ holds for all $n \ge 2$. Now, my ...
0
votes
1answer
47 views

help on manipulating this algebraic expression

So I have something like: $\frac {k!}{(k-3)!3!}$ I'm going to add $\frac 12k(k-1)$ to this, and I want to obtain $\frac {(k+1)!}{(k-2)!3!}$ as the result. I'm having trouble with this since I need ...
2
votes
2answers
66 views

Induction: $2^n = \sum_{v=0}^{n} \binom{n}{v}$ [duplicate]

I have to prove the following identity for $n \in \mathbb{N}$: $\displaystyle 2^n = \sum_{v=0}^{n} \binom{n}{v}$ Is there a way to show it through induction? Or is there a easier way? My steps so ...
1
vote
0answers
62 views

How to use an exponent that contains a variable

I am trying to understand a problem that uses mathematical induction to prove the validity of a statement. This is how one section moves to another: $$ 2k + 3 = 2^{k + 1} $$ $$ 2k + 3 = (2k + 1) + 2 ...
3
votes
3answers
96 views

Integers whose sum and product are integers

Let $a$, $b$ be real numbers such that $a + b$ and $ab$ are integers. a. Prove that $a^n + b^n$ is an integer for every natural number $n$. b. Suppose that $a$ does not equal $b$. Prove that ...
-2
votes
2answers
94 views

Mathematical induction or what ??

Simplify $$\left(x+\frac1x\right)\left(x^2+\frac1{x^2}\right)\left(x^4+\frac1{x^4}\right)\ldots\left(x^{2^{n-1}}+\frac1{x^{2^{n-1}}}\right)$$ for $n\in\Bbb N$. how to solve this problem, and am I ...
0
votes
4answers
281 views

Induction: Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \frac{\sin(nx)\sin((n+1)x)}{\sin(x)}$

Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \dfrac{\sin(nx)\sin((n+1)x)}{\sin(x)}$ I tried to use induction. Base case is easy, but I'm stuck at the induction step (from $k$ to $k+1$). ...
2
votes
3answers
187 views

Algebra Textbook

Perhaps this questions was asked already, but I browsed through other threads and couldn't find exactly what I am looking for. I am looking for an Algebra Textbook (high-school/undergrad level) that ...
1
vote
1answer
92 views

The sum of odd powered real numbers equals zero implies the numbers are inverses

Show that if real numbers $a_1,a_2,\ldots,a_n$ satisfy $$a_1^l+a_2^l+\cdots+a_n^l=0$$ for every odd $l$, then for any $a_i$ we can always find some $a_j$ (not necessarily different) such that ...
2
votes
1answer
71 views

if its true for $n$ is it true for $n-1$ (mathematical induction)?

the induction rule , if we suppose that $p(n)$ is true , is $p(n-1)$ true as well? if $1+2+...+n=\frac{n(n+1)}{2}$ is it true than $1+2+...+n-1=n-1(n-1)/2$ (before proving the statement for $p(n+1)$ ...
-1
votes
1answer
87 views

Simple Question about Induction?

let x be a natural number i want to prove that f(x)=$x^2$. suppose that f(x)=$x^2$, f(0)=0 holds we'll prove that f(x)= $(x+1)^2$, in the functional equation we have f(x-y)+f(x+y)=2f(x)+ stuff, ...
3
votes
2answers
140 views

Prove that $2^n>2n$ for all integral values of n greater than 2 [duplicate]

Prove $2^n >2n$ for all integral values of n greater than 2. Let $p_n$ be the statement: $$2^n>2n\ \forall\ n\gt2$$ If the inequality is valid for $n=k$ where $k>2$: $$p_k: 2^k>2k$$ ...
2
votes
4answers
541 views

For what natural numbers is $n^3 < 2^n$? Prove by induction

Problem For what natural numbers is $n^3 < 2^n$? Attempt @ Solution For $n=1$, $1 < 2$ Suppose $n^3 < 2^n$ for some $n = k \ge 1$ It looks like the inequality is true for $n = 0$, $n = 1$ ...
5
votes
2answers
269 views

Suggestions on how to prove the following equality. $a^{m+n}=a^m a^n$

Let $a$ be a nonzero number and $m$ and $n$ be integers. Prove the following equality: $a^{m+n}=a^{m}a^{n}$ I'm not really sure what direction to go in. I'm not sure if I need to show for $n$ ...
1
vote
1answer
72 views

Prove inequality by induction

Once again, I'm stuck in a demonstration by induction, this time, it's really proving that an inequality is valid. So, here is the inequality: Prove that $\binom{2n}{n} \geq (n+5)^2 \ \forall n ...
3
votes
3answers
80 views

A proposed proof by induction of $1+2+\ldots+n=\frac{n(n+1)}{2}$

Prove: $\displaystyle 1+2+\ldots+n=\frac{n(n+1)}{2}$. Proof When $n=1,1=\displaystyle \frac{1(1+1)}{2}$,equality holds. Suppose when $n=k$, we have $1+2+\dots+k=\frac{k(k+1)}{2}$ When $n = k + ...
0
votes
1answer
81 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
0
votes
2answers
88 views

Two exercises on mathematical induction

Studying for a test and can't work out how to do two questions on the sample test. (1) Suppose a sequence of numbers $a_1$, $a_2$, $\dots$ is defined recursively by: $$a_1 = 1\qquad\text{and}\qquad ...
0
votes
2answers
126 views

I need help with proofs using mathematical Induction

I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
0
votes
1answer
69 views

Prove by induction $ \sum^n_{i=1}(i-1/2) = n^2/2 $

This is a question from a test that I wrote and I'm wondering how do you solve it. Prove by induction that $$ \sum^n_{i=1}(i-1/2) = \frac{n^2}{2} $$ *Provide a Base Case, Inductive Hypothesis, and ...
1
vote
1answer
96 views

prove sum property by induction

Knowing that $(a_i)_{i\ge1}$ prove that $\forall n \in \Bbb N$: $$\sum^n_{i=1}ra_i=r\Big(\sum^n_{i=1}a_i \Big)$$ This kind of demonstrations is totally strange to me, I do not understand how to ...
2
votes
2answers
78 views

Check proof by induction of $\sum_{i=0}^n i^4 = \frac15 n^5+\frac12n^4+\frac13n^3-\frac1{30}n $

$\forall n \in \Bbb N$, I must demonstrate that: $$\sum_{i=0}^n i^4 = \frac15 n^5+\frac12n^4+\frac13n^3-\frac1{30}n $$ $\bullet$ I need to prove that this is true for the first element of the sum (1): ...