text:
# Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

(Java Code on Github at the bottom of the post. )

Q: What is the unknown?
A: the indices of the two numbers in the array that add up to a target value.
Q: What are the data?
A: An array of integers and a target value.
Q: What are the constraints? Ambiguities?
A: The index is not zero-based. The example gives us a sorted array but it may not be sorted in other cases. There may be duplicates in the array.
Q: Have you seen this problem before?
A: Yes, but I want to redo this problem like a clean slate rather than memorize the solution to it.
Q: How do we approach it?
A: One possible solution would be for each element in the array, subtract it from the target value and check if the remained value is also in the array. But that would take O(n^2) time (and O(1) space).
Q: So can we do better? If we can, what is the bottleneck?
A: The bottleneck is that we have to scan through the whole array to see if a value exist. If we can speed up this lookup process, it would help to speed up the whole algorithm. Current lookup is O(n) and possible upgrades are O(logn) and O(1). Now what algorithm or data structure can achieve O(logn) and O(1) lookup? I would say BST and Hashtable. Since both data structure uses O(n) space, we will consider hashtable since it is faster in lookup.
Q: OK, so how does hashtable lookup fit in here?
A: Well, I think we need to scan through the array first and count the frequency of each value. Then in the second pass, we calculate the remained value by subtract the current value from the target and check if the remained value exists in the hashtable. If not, we move on to the next one. If yes, then we have found one (here be careful about duplicates and values like 4-2=2).
Q: Yes, we can do that, but the problem asks for the index of the two numbers, not the numbers themselves.
A: Ah yes, we can use another hashtable to keep track of the indices of each value or we can scan through the array to find the index of these two values. The first way require extra O(n) space while the second way requires an extra pass of O(n) time.

Q: OK, one question: is it possible that an number overflow happens in your algorithm? If yes, how do you solve it?
A: Suppose that our target value is Integer.MIN_VALUE + 1 and our array is [3, -1, Integer.MIN_VALUE + 2]. In this case, if we subtract 3 from our target value, we will get out of Integer range. Similarly, if our target value is Integer.MAX_VALUE – 3 and our array is [-4, 1, Integer.MAX_VALUE – 4], we will get the same type of problem when we subtract -4 from our target value. So it looks like that we need to validate the range before subtracting.
Q: Yes, you got this part right. Now do you have any idea of how to do it?
A: Well, the target value is in range. Basically we need to check if we subtract the current value from the target, would it be outside of [Integer.MIN_VALUE, Integer.MAX_VALUE]? To get lower than Integer.MIN_VALUE, we need to subtract a positive number from the target. To get higher than Integer.MAX_VALUE, we need to subtract a negative number from the target. So if the current value is positive, we check if the MIN plus current is larger than the target. If yes, then it’s going to be out of bound if we do the subtraction. Similarly, if the current value is negative, we check if the MAX plus the current value is smaller than the target. If yes, then it’s going to be out of bound if we do the subtraction. Two examples here:
Say the range is [-10, 10]. target value is 3, current value is -8. 10-8 = 2 is smaller than 3, so this is going to be out of bound.
if the current value is 9, -10 + 9 = -1 is smaller than 3, so subtracting 9 from 3 is OK. We can even drop a graph to illustrate this idea.

Q: GOOD, you got it. Make sure you implement the code. Any other way to solve this problem?
A: Well, yeah we could sort the numbers first but that messes up the index and we have to keep track of the previous index somehow. So that’s not worth it in this problem. If we are only looking at the numbers, this approach may save us some spaces.

Code on github:

# Interactive documents: An incredibly easy way to use Shiny

Awesome new features!

# Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: To reverse nodes in a linked list k at a time and return the modified list.

Q: What are the data?

A: A linked list and an integer k.

Q: What are the constraints?

A: From the example above, we should probably assume this is a singly linked list. We cannot change the value in the node (Actually this is a very good idea in modifying linked list). Constant memory only. If at some point, the number of nodes is not the multiple of k, these nodes should remain the same order.

Q: Have you seen it before or at least something similar?

A: Yes I think I have. A similar problem is to reverse a singly linked list in place. I solved it before and it only took constant memory. I think we can apply the solution of that problem to each K nodes for reversing purpose.

Q: Good. For the whole problem, what kind of strategy should we use? Suppose we have reversed K nodes in the list, what about the rest of list?

A:  We do the same for the rest and connect with the k nodes reversed previously.

Q: Can you describe it in more details?

A: OK, for the rest of the linked list we reverse the nodes in k-Group and connect with previously reversed k nodes. Ah I see where this is heading. We are looking at a recursion here.

Q: Yes we are. Now think about the base case of this recursion.

A: That would be the number of remaining nodes is not a multiple of k and we should just connect them with the previously reversed part.

Q: What about the recursive case?

A: Hmm, we should reverse the current k nodes at hand. reverse the next k nodes and connect with them. Then return the current reversed part so the previously reversed part can connect with it.

Q: OK not super clear but I guess you have the idea.  In the base case, how do you determine if the number of remaining nodes is a multiple of k?

A: Starting from where we are, go k steps further. If at any point, we hit null, then we know there are enough nodes for reversal.

Q: Good. The take-away message here is that recursion could be a very handy trick for solving linked list related problems. So keep it in your toolbox.

Code on github:

# Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: A program that solves Sudoku.

Q: What are the data?

A: A Sudoku puzzle. Actually a 9 x 9 character matrix, with partially filled cells. Empty cells are represented as ‘.’

Q: Any constraints?

A: None except for the Sudoku rules:

• Each row must have the numbers 1-9 occuring just once.
• Each column must have the numbers 1-9 occuring just once.
• Each block (check the link above for details about block) must have the numbers 1-9 occuring just once.

Q: Have you played Sudoku before?

A: Not even once. I guess this is my first and last attempt to play Sudoku. Based on the rules, I guess I have an idea for solve it. Just like the N-queens problem we solved last time, we will probably need backtracking: At an empty cell, I try to find a suitable number from a set of candidates to put it there and then move on to the next empty cell. If one does not work out, I find the next suitable number. If none of the candidates works out, then the number I placed at the previous empty cell was a bad choice and I need to go back to deal with it. This seems like a pattern that requires backtracking.

Q: Good, now to work with backtracking, are there anything you need?

A: Yes, I believe we need something to keep track of whether I could place a number in an empty cell or not, and a set of candidates for each empty cell.

Q: How do you know if you can place a number in an empty cell or not?

A: Hmm I have to check the row, column and block it resides in to see if that number already exists. The empty cells on the same row will share the info of this row. The same applies to columns and blocks. So we need three 9 x 9 boolean matrix: rowStatus, colStatus and blockStatus. Initially all values are set to false. If a number n is placed at cell (i, j), then we go and update rowStatus[i][n-1] = true, colStatus[j][n-1]=true, and blockStatus[getBlockInd(i,j)][n-1]=true.

Q: Good. Now what about the candidates for each empty cells you mentioned? It seems like you need to keep a lot of numbers at hand.

A: Hmm not necessarily. For each cell, there are only 9 options at most. I could try all of them every time but that seems a bit brutal. I could keep track of a number called startInd to save the index of the last number I tried at a certain cell. Next time I need another number at this cell, just get the number at the next index. If the next index is out of bound, that means none is a good fit. In that case, we set the  startInd of this cell to 0 and go backtracking to the previous cell.

Q: Sounds good. Now can you write some pseudo-code?

A: Sure.

// Initialization
// scan through the board and keep track of all the empty cells
emptyCells = getEmptyCells(board);
// update the status based on the initial board

int i = 0; // the index of an empty cell we are dealing with
while(true){
Cell cell = emptyCells.get(i);
int row = cell.row;
int col = cell.col;
char num = getSuitableNum(row, col, rowStatus, colStatus, blockStatus);
if(num == '.'){ // no suitable num, previous bad choice
if(isOutofBound(--i, emptyCells.size())) return;
Cell previousCell = emptyCells.get(i);
row = previousCell.row;
col = previousCell.col;
char previousVal = board[row][col];
board[row][col]='.';
undoStatusChange(rowStatus, colStatus, blockStatus, row, col, previousVal);
}else{
board[row][col] = num;
updateStatusChange(rowStatus, colStatus, blockStatus, row, col, num);
if(isOutofBound(++i, emptyCells.size())) return;
}
}

// for details of utility functions like undoStatusChange, isOutofBound, and getSuitableNum, please check the real Java code at the bottom link.

Q: I see you are passing the rowStatus, colStatus and blockStatus around a lot. Is there anyway that we can organize them in a better way?

A: Hmm maybe I should put them all in one Class so I could just pass in one object instead.

Q: Sounds good, now let’s solve this with real code.

A: OK 🙂

Code on github:

# N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]

A follow-up question: Now, instead outputting board configurations, return the total number of distinct solutions.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Well, this is a classic problem, isn’t it? However, all I know is that it’s classic and I’ve never really read about any article of NQueens, except for the title NQueens. So lucky for me, I got the chance to solve it with no prior knowledge.

Q: What is the unknown?

A: All possible board configurations that satisfy the requirements.

Q: What are the data?

A: An N x N chess board (or just an N x N matrix).

Q: What are the constraints?

A: No two queens on the board can attack each other. In other words, no two queens can be on the same row, column or cross.

A: I don’t have anything fancy, but possibly a naive way of solving it: for example, I could put a Queen in an available cell (no other Queens can attack) on the chess board. Then cross out all other cells this Queen can attack. Then on the second row, I place another Queen in an available cell and then cross out cells she can attack. On the next row I do the same thing until we place all N Queens on the chess board.

Q: What if on a certain row, there is nowhere you can place a new Queen?

A:  Hmm, that means the placement of the Queen on the previous row was a bad move.

Q: So what should you do about it?

A: Well, undo it then. Undo the cross out of board cells caused by that bad move. Get the queen up and place it somewhere else on that row, if there are any available cells left.

Q: What if there are no available cells neither?

A: Hmm, then the bad move’s previous move was bad. We have to do the same thing for it as above.

Q: Good. Now, can you summarize your thought and maybe find out the pattern in it?

A: I place a Queen in an available cell on a row, and cross out cells she can attack. Then on the next row, again I place a Queen in an available cell and cross out cells she can attack. If I cannot place any Queen, that means the previous move was bad and we undo that move and its cross-out, then place that Queen in another available cell. If that’s not possible, then the previous previous move was bad and we should….  OK I get it. This has something to do with recursion, doesn’t it? And in fact, even if we find a solution, we still need to undo previous move and its cross-out since we are looking for all possible solutions, not just one. Other moves may also lead to solutions.

Q: Good catch. Now can you think of an abstract version of your thoughts? Possibly some pseudo code?

A: OK. So if we are dealing with recursion, we should always think about base case and recursive case. The base case should be that N queens are all on the board. Maybe we should keep track of how many Queens on the board? Or on the second thought, maybe not. Based on my thoughts above, since we are moving to the next row if and only if we can place a Queen on the current row, a solution is found if we are on row N (row index from 0 to N-1). This is the time we stop recursion and return the current board configuration.

// suppose we call this function solveNQueens

// base case
if (rowInd == N) {
SaveTheBoard(board);
return;
}

OK, moving on to the recursive case. I don’t want to repeat myself again so let’s look at some pseudo codes.

// since we want all possible solution, we should check all possible cells. Therefore we use the loop. Say we are on row K.
for(int i = 0; i < N; i++){
if (isAvailable(board[K][i])){
placeTheQueen(board, K, i);
crossOutCells(board, K, i);
solveNQueens(board, K + 1, N);
undoPlaceAndCrossOut(board, K, N); // always undo
}
}

Q: Good. Just one question before we move on to real code. How do you plan to do the cross out and undoCrossOut?

A: Oh I could create a boolean matrix[N][N] and if a cell is crossed out, set the corresponding cell to true. In undoCrossOut just set it to false.

Q: Hmm, not quite. Think about this: A cell C2 on the second row is set to true (crossed out by a Queen on the first row). You place a Queen on the second row somewhere and C2 gets crossed out again (set to true). Later you find that your move on the second row isn’t ideal. You undo the move and C2 is set to false. That doesn’t seem right. Since it can be attacked by the Queen on the first row.

A: Hmm, then I guess I can use an integer matrix then. Every time a cell gets crossed out, we increase the value in the corresponding cell. As long as the value in a cell is greater than 0, it is not available.

Q: Sounds good. Now go on to do some real coding.

Code on github:

Now for the follow up question, it is actually simpler. We don’t even need the board. All we need is just a counter and we increase the counter only in the base case. But sure to return the counter. (The code below mentions a mistake I made about Integer type)

# Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What’s the unknown?

A: The next permutation of the current sequence.

Q: What’re the data?

A: An integer array representing a number.

Q: Any Constraints?

A: No extra memory allocation allowed. But I think it means extra memory proportional to the input size N. Besides, at the beginning of solving this problem, we can ignore this constraint.

Q: True. Now what’s the meaning of next permutation?

A: Hmm, I think it means the next number sequence of the current sequence in lexicographic order, e.g., (1,2, 5, 3,4) -> (1,2, 5, 4,3), (1, 5, 3,4,2) -> (1, 5, 4,2,3) and (5, 4,3,2,1) -> (1,2,3,4,5).

Q: Now as a human being, how do you do this?

A: Eh..just think of the smallest number comprised of these digits that is greater than the current sequence. If there is none, we go back to the smallest possible number in all permutation.

Q: OK, but a computer can’t just “think of” the next number. Now how would a computer do that?

A: Hmm, I think we probably need to start with the least digit on the right side. But what next?

Q: Look at the example you listed above. What did you do with each example?

A: In (1,2, 5, 3,4) -> (1,2, 5, 4,3), I start with 4 and look at its left digit, 3. Since 3 < 4, I switch them. Hmm this works for all cases where the second digit is less than the first one. In (1, 5, 3,4,2) -> (1, 5, 4,2,3), I can’t switch 4 and 2 since (1,5,3,2,4) precedes (1,5,3,4,2). Well 3 < 4, I could switch them to get (1,5,4,3,2) but that’s not the correct answer. Hmm…

Q: So how do you get from (1,5,4,3,2) to (1,5,4,2,3)?

A: I could just switch 3 and 2.

Q: OK, what about (1,5,3,4,2,0) to (1,5,4,0,2,3)?

A: Hmm if I switch 3 and 4, I get (1,5,4,3,2,0). To get (1,5,4,0,2,3), I need to reverse 3,2,0 to 0,2,3. OK, I guess we should do like this: scan from the right, find the first digit at index Ind that is less than its previous digit, switch them and reverse the sequence to the right side of Ind.

Q: Well, almost there, but not yet. What about (1,6,3,5,4,0)? According to your algorithm above, the next permutation becomes (1,6,5,0,4,3) while it should be (1,6,4,0,3,5). See the problem?

A: Hmm, so 3 should be the switch point. I got that right, but it should switch with 4 instead of 5. Ah, so 3 should switch its ceiling in the sequence on its right side! We need to go back to find it and swap. Then do the reverse operation.

Q: Correct, what about the time complexity?

A: We scan the sequence and once find the switch point, we go back and find its ceiling, then switch and reverse. End of story. So it’s actually O(n), an linear time algorithm.

Code on github:

# Nuts and bolts

Nuts and bolts. A disorganized carpenter has a mixed pile of N nuts and N bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses NlogN compares (probabilistically).

My thoughts and solution:

Well, according to the question, the nut and bolt has a one-to-one relation. So the first thing come into my mind is to sort the nuts and bolts into ascending order and then we can put them together to a pair one by one.

However, we cannot compare two nuts or bolts directly. So we have to think about indirect ways. Say we have two nuts N1 and N2. Well, since the nut and bolt has a one-to=one relation, there must exist two bolts B1 and B2 which exactly fit with N1 and N2. So if we try to fit both nuts with B1 (or B2), we can tell which nut is bigger. This is also suggested by the question that By fitting a nut and a bolt together, the carpenter can see which one is bigger”. The same works for comparing B1 and B2 indirectly.

OK, the question did mention NlogN compares probabilistically. Well that reminds me of QuickSort. So how does it apply here? QuickSort requires partitioning and recursion. OK, let’s look at partitioning.

To partition the nuts, we need to randomly select one nut, then compare it with the rest. But we cannot, at least not directly. So the alternative is to randomly select one bolt “B”, then compare each nut with it. In the end, we will have two small piles of nuts (one smaller than the bolt “S” and the other larger “L”) and the right one fits in the bolt “N”. Done!

Then we can do recursion, right? for both piles of nuts, randomly choose a bolt to partition…But wait! Whatever bolt we pick for “S” should come from the set of bolts that correspond to the nuts in “S” and so is the case for “L”. Otherwise, we cannot guarantee the correctness of the QuickSort algorithm.

So before we do the recursion, we have to find out the corresponding piles of bolts for “S” and “L”. How? Well, we do know the nut “N” that fits into “B” perfectly. We can do a partition of the bolts based on “N”. Then we will get our desired piles of bolts for “S” and “L”.

Now we can go on to the recursion.

About the comparison, it is O(NlogN). But I’m afraid we are using 2NlogN since we compared 2N in partitioning  the bolts and nuts. If you have some good ideas, please leave some comments.

# Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

OK, how hard can this be, right? just find the first integer n such that n * n <= x and (n+1) * (n + 1) > x. Well mathematically this is correct, but if we transfer this idea to a program directly, we may run into the following two problems:

• Time Limit Exceeded (well the OJ has a time limit for this question. O(N) is not acceptable)
• Integer Overflow! It is possible that n*n is greater than the limit of Java integer (from -2^31 to 2^31 – 1).

I was stuck. Then someone on the discussion board mentioned: Think about math back in elementary school. n * n <= x is equivalent to what? Stupid me, n <= x / n. So if we avoid using plus and multiplication in comparison, we can avoid the integer overflow problem using subtraction and division. And I think this idea can extend to other primitive types as well. For something like (a+b)/2 we could re-write as a/2 + b/2.

As for the time limit problem, we can consider two improvements:

• The naive algorithm would go from 1 to x. This is not necessary. We can simply check from 0 to x/2. Why? Because when x > 4, (x/2)^2 is always larger then x.
• Is it necessary that we must go for a linear search? It’s a sorted sequence from 1 to x/2 and we are trying to find a number with a certain property. And this reminds me of binary search.

With these three improvements,  we can solve this question efficiently.

Code on github:


text:
# Brownian motion: changing the order of expectation and integration in $E \left( \int_s^t B_x dx \mid F_s \right)$

Let $B$ be a standard Brownian motion with induced filtration $F$.
Is it true that, for $s<t$, $$E \left( \int_s^t B_x dx \mid F_s \right) = \int_s^t E \left( B_x \mid F_s\right) dx \;?$$

To prooved this, I would use the dominated convergence theorem.
But I don't see any dominating function.
Viewing the integral as a standard Riemann integral, I think the result follows.

-

Write $B_x=B_x-B_s+B_s$. By linearity of conditional expectation and using the fact that $B_x-B_s$ is independent of $\mathcal F_s$, we are reduced to show that $$E\left(\int_s^t(B_x-B_s)dx\mid\mathcal F_s\right)=0.$$ It's enough to show that $\int_s^t(B_x-B_s)dx$ is independent of $\mathcal F_s$. To see that, write $\int_s^t(B_x-B_s)dx$ as the almost sure limit of $\frac 1n\sum_{j=0}^{n-1}(B_{s+xk/n}-B_s)$. If $X_n$ is independent of $Y$ for all $n$ and $X_n\to X$ almost surely, then $X$ and $Y$ are independent. Indeed if $O_1$ and $O_2$ are open, $$P(X\in O_1,Y\in O_2)=\lim_{n\to +\infty}P(\bigcap_{j\geq n}X_n\in O_1,Y\in O_2)=\lim_{n\to +\infty}P(\bigcap_{j\geq n}X_n\in O_1)P(Y_n\in O_2),$$ and we conclude by a monotone class argument (I should introduce the set of probability one where we have the convergence).

format: plain


text:
## 22 January 2008

### Data is the New Long Distance

I just finished a two year Verizon Wireless contract. They frantically called me, informed me my contract was up, and walked me through a month-to-month agreement. The only change was that their "Mobile Web" feature went from $5/monthly to free. Free! Sweet! Then I listened to the big long details where the customer service rep informed me they didn't debit my airtime minutes for the usage. Charges now run$1.99/megabyte for Mobile Web usage unless you spend $15+ monthly on an all-you-can-eat option. That straw, the allure of SIM cards, and the fact that Verizon has the lousiest, P.O.S. software on their phones (contact me if you're interested in a rant) made me switch to at&t yesterday. I paid attention to at&t's data charges— either$15+ monthly for a smörgåsbord or $0.01/kilobyte. Similarly crazy in price. An example of the sheer monstrosity of it all: • Assume you didn't pay the$180+ annually these companies want for unlimited data plans
• Assume you bought a 2 gigabyte microSD card for your phone.
• Assume you filled up your microSD card
All of these seem reasonable. After all, you're already paying hundred of dollars annually to be able to use the phone you've purchased. For 2 gigabytes/2,048 megabytes/2,097,152 kilobytes of a la carte data:
• Verizon would charge you $4,075.52 to fill a 2 gigabyte microSD card at$1.99/megabyte.
• at&t would charge you $20,971.52 to fill a 2 gigabyte microSD card at$0.01/kilobyte.

The wireless carriers may rationalize this ridiculousness by saying that they can better forecast data network needs when customers buy unlimited plans. But then again, how much forecasting information do you get on "unlimited" plans?

Monthly a la carte data plan pricing should cap out at the monthly unlimited plan rate. After using \$15 bucks of a la carte data in one month, just bump me to unlimited already. Say that up front. Don't be shady. Sheesh.

#### 1 comment:

Erik said...

Or should cap out at least twice the price or something. Thats why I always liked Sprint's fair and flexible plan which caps out at the next higher level than what you paid for...


text:
# Correct standard form for the equation of a line?

So I was tutoring an Algebra 1 student yesterday and we were reviewing the three forms in which one can write the equation for a line: point-slope form, slope-intercept form and standard form. I told him to write an equation in standard form and he wrote:

$\frac x5 + \frac y4 = 1$ and I told him to rewrite it without any fractions as $4x +5y = 20$

Are both forms correct? I understand that the latter form may be more common but what I really want to know is if it is acceptable to use the former. Thanks all!

The first form is usually called intercept form. That's because if you can write the equation in the form $\frac{x}{a} + \frac{y}{b} = 1$, then the $x$-intercept is $a$ and the $y$-intercept is $b$.
General form isn't unique, but intercept form is a specific variety of the general form in which the constant term is $1$ and is isolated on one side, and the coefficients of the variables are written as fractions with numerator $1$.
I have been taught that the standard form is: $$Ax + By + C = 0$$ Where A, B, and C are all integers, and A must be positive. So the latter part is correct. For example, if I have a "messy" equation in slope-intercept form, $$y = x/2 + 3/4$$ I would have to multiply both sides by 4, giving me the equation: $$4y = 2x + 3$$ Because the coefficient of the x term has to be positive, I will move 4y to the right, which gives: $$2x - 4y + 3 = 0$$ I hope this answer helped!


text:
# Can't argue with success? Looking for “bad math” that “gets away with it”

I'm looking for cases of invalid math operations producing (in spite of it all) correct results (aka "every math teacher's nightmare").

One example would be "cancelling" the 6s in

$$\frac{64}{16}.$$

Another one would be something like

$$\frac{9}{2} - \frac{25}{10} = \frac{9 - 25}{2 - 10} = \frac{-16}{-8} = 2 \;\;.$$

Yet another one would be

$$x^1 - 1^0 = (x - 1)^{(1 - 0)} = x - 1\;\;.$$

Note that I am specifically not interested in mathematical fallacies (aka spurious proofs). Such fallacies produce shockingly wrong ends by (seemingly) valid means, whereas what I am looking for are cases where one arrives at valid ends by (shockingly) wrong means.

Edit: fixed typo in last example.

• @rschwieb: I don't understand your comment at all. The OP is asking for examples where, by wrong means, you end up with a correct result, and not where by "seemingly" valid means, you end up with a wrong result. It does not matter how you interpret "seemingly"; any "proof" that ends up with a wrong conclusion should not be posted as an answer here. That's the OP's choice. – TMM Dec 17 '12 at 14:30
• This is reminding me of an anecdote about a physicist from the early 20th century with a reputation for making arithmetic errors who as a joke intentionally made a huge order of magnitude error (10^10???) in a published paper; and then published a correction the next month noting that the error didn't affect the results of the computation. Unfortunately I'm failing to Google it so I can't see if what he did would be relevant to this question or not. – Dan Neely Dec 17 '12 at 16:52
• The College Mathematics Journal used to have a section entitled "Fallacies, Flaws, and Flimflam." It regularly featured exactly these kinds of things. – Mike Spivey Dec 17 '12 at 18:54
• Why is this on topic? – Anko Dec 17 '12 at 21:11
• There is a whole book about this "Mathematical Fallacies, Flaws, and Flimflam". This book is exactly what you are looking for. It has scores of such examples in a whole bunch of categories like algebra, calculus, multi-variable calculus, and so on. Love this book! – Fixed Point Dec 17 '12 at 21:17

I was quite amused when a student produced the following when cancelling a fraction:

$$\frac{x^2-y^2}{x-y}$$

He began by "cancelling" the $x$ and the $y$ on top and bottom, to get:

$$\frac{x-y}{-}$$

and then concluded that "two negatives make a positive", so the final answer has to be $x+y$.

• That’s downright spectacular; I don’t think that I ever had a student do something quite that ... impressive. – Brian M. Scott Dec 17 '12 at 12:09
• When I showed another student that you can cancel 6s in $16/64$ and $26/65$ to get the right answer, his response was: "so ... you can cancel digits only if they are 6?" – Old John Dec 17 '12 at 12:12
• I’ve always been fascinated by students’ ability to come up with the wrong generalization. – Brian M. Scott Dec 17 '12 at 12:15
• @OldJohn Maybe you could have shown him $\frac{95}{19}=\frac{5}{1} = 5$ after "cancelling the $9$'s" so he could have generalized further to "cancel digits only if they are $6$, right-side-up or upside down" – Dilip Sarwate Dec 17 '12 at 12:31
• @orokusaki What we are really talking about is that the correct answer IS obtained, but by a hopelessly invalid method. – Old John Dec 17 '12 at 19:37

Here's a pretty funny one from xkcd.

• Maybe this could be explained? I had to Google for what it meant because I have never learned to write down a division like that. – sam hocevar Dec 18 '12 at 13:50
• It is ridiculous how a student knows about radicals and division before learning their multiplication tables. ;) – Parth Kohli Dec 19 '12 at 9:51
• In case anyone doesn't get it, it reinterprets $3\sqrt{81}$ as $3)\overline{81}$ which is American long division notation for 81/3. He covers for failing to change the symbol by actually writing out the schoolbook division steps. – Random832 Dec 22 '12 at 0:13
• Algebraically, $x \cdot x^2 = x^4/x$. – Antonio Vargas Feb 27 '14 at 14:45

A student in a test was asked to give an example of two irrational numbers whose sum is irrational.

He chose $x = \sqrt{2}$, and $y=\sqrt{3}$, and computed the sum $x+y$ using a calculator. Unfortunately, he only took two digits, which led to the following:

$x = 1.41$, and $y = 1.73$, which implies that $x+y = 3.14$.

The student concluded that $\sqrt{2}+\sqrt{3}=\pi$.

• Well he was approximately right! – fluffy Dec 17 '12 at 22:39
• Hmm but OP is looking for true conclusions based on a flawed process. – alex.jordan Dec 18 '12 at 0:30
• You are right, Alex. But it's so funny that I couldn't resist... – the L Dec 18 '12 at 9:10
• @alex.jordan: Well the conclusion that $\sqrt{2}+\sqrt{3}$ is irrational is indeed true. – Cheerful Parsnip Dec 18 '12 at 17:33
• math.stackexchange.com/questions/701822/… – Daniel McLaury Sep 18 '14 at 11:11

Here's another classical freshman calculus example:

Find $\frac{d}{dx}x^x$.

Alice says "this is like $\frac{d}{dx}x^n = nx^{n-1}$, so the answer is $x x^{x-1} = x^x$." Bob says "no, this is like $\frac{d}{dx}a^x = \log a \cdot a^x$, so the answer is $\log x \cdot x^x$." Charlie says "if you're not sure, just add the two terms, so you'll get partial credit".

The answer $\frac{d}{dx}x^x = (1 + \log x)x^x$ turns out to be correct.

• That's not wrong; that's a perfectly valid method. You get the derivative of any expression with respect to $x$ as the sums of all the derivatives with respect to the individual instances of $x$ while holding all other instances constant. – joriki Dec 18 '12 at 13:34
• I guess this is an example of using a correct method for incorrect reasons. – Cheerful Parsnip Dec 18 '12 at 17:32
• @ Joriki: You just gave me a "eureka" moment with that comment (generalizing multiple instances of the same variable to multivariable calculus). – Joe Z. Feb 12 '13 at 16:25
• You could also "prove" the product rule like this. – Baby Dragon Oct 12 '13 at 6:05
• This "rule" also is useful for deriving an integral in which the variable is both inside the integral and in the limits en.wikipedia.org/wiki/Leibniz_integral_rule#Formal_statement – leonbloy Nov 2 '13 at 21:46

Typesetting "errors" in which exponents or multiplication signs are omitted but the resulting expression is equivalent to the original one. Examples include \begin{align} 2^5 9^2 &= 2592, \\ 3^4 425 &= 34425, \\ 31^2 325 &= 312325,\end{align} and $$2^5 \cdot \frac{25}{31} = 25 \ \frac{25}{31},$$ where a whole number followed by a fraction is interpreted as a mixed fraction (e.g., $1 \frac{1}{2} = 1 + \frac{1}{2} = \frac{3}{2}$).

That page also contains a link to your first example of "cancelling" 6s, denoted "Anomalous Cancellation", and containing three other examples with both numerator and denominator less than $100$: $$\frac{98}{49} = \frac{8}{4} = 2, \qquad \qquad \frac{95}{19} = \frac{5}{1} = 5, \qquad \qquad \frac{65}{26} = \frac{5}{2}.$$

• Thanks for the pointer. That page also lists all the "all proper solutions up to 3-digit denominators" (where "solutions" are fractions amenable to "anomalous cancellation"), but for some reason it does not include fractions like 101/202. It also does not mention that the four examples with 2-digit denominators are particularly productive: 2666666/6666665 = 2/5, 499999/999998 = 1/2, etc. – kjo Dec 17 '12 at 15:27

This one is from Mathematical Fallacies, Flaws, and Flimflam - Edward J. Barbeau.

A student on a quiz was asked to integrate $\displaystyle \int \frac{1}{1+x}\;{dx}$. His/her answer was as follows:

\displaystyle \begin{aligned} \int \frac{1}{1+x}\;{dx} &= \int \bigg(\frac{1}{x}+\frac{1}{1}\bigg)\;{dx} \\& = \int \frac{1}{x}\;{dx}+\int\frac{1}{1}\;{dx} \\&= \log(x)+\log(1) \\&= \log(x+1)+C. \end{aligned}

• Actually the first $dx$ is missing in the book. I'm not sure whether the solution of the student was as such or whether it's a typo in the book. It's probably how the student wrote it. Anyway, that book contains many interesting examples of this, as well as non-trivial faults with solutions that arrive preposterous conclusions! (The one above this one for example arrives at the conclusion that every derivative is continuous!). – NeverBeenHere Dec 17 '12 at 22:27
• Strange that the $C$ appears in the last line but not in the one before. As you say, it must be how the student wrote it. – joriki Dec 18 '12 at 13:55
• @Joriki Yeah, perhaps I shouldn't have added the first $dx$ as well! – NeverBeenHere Dec 18 '12 at 19:08
• That was a test by the student to see if teacher reads the proof – nicolas Nov 10 '14 at 18:47
• Furthermore, log(a)+log(b) is not equal to log(a+b) – BadAtGeometry Mar 31 at 0:04

I dont't know if this counts. But I really like it. Let $A$ be a square matrix over a field $K$ and $$\chi = \det(X \cdot \operatorname{Id} - A) \in K[X]$$ the characteristic polynomial of $A$. Then $\chi(A) = 0$, because "it's just plugging in".

• I bet you can set things up in terms of matrices over the ring $K[A]$ so that you really can just plug things in to prove the theorem. – Hurkyl Dec 17 '12 at 18:16
• Yes I think "we" can, but not the students. Most often they have difficulties to see what they are doing wrong by just plugging in. – Hans Giebenrath Dec 17 '12 at 18:27
• @akkkk: What do you mean? He mentions the above "proof", but calls it wrong and encourages students to find the error. Hence I don't understand the "Unfortunately". – InvisiblePanda Dec 17 '12 at 22:15
• This is a great example which cannot be made rigorous, at least not in any simple way. For example such an argument has to take into account that $A$ does not satisfy the equation $\mathrm{tr}(A-X\cdot I)=0$. – Morgan Sherman Dec 17 '12 at 22:27
• @Marc: You can define the determinant for matrices over any commutative ring. The ring $K[A]$ is commutative, and so matrices over $K[A]$ have determinants in $K[A]$. – Hurkyl Dec 18 '12 at 16:37

I was once writing something where for stylistic reasons it made sense to change the way I wrote a vector of non-negative integers by writing $(a_1,\dotsc,a_n)$ as $1^{a_1}\dotsm n^{a_n}$, like a product, and omitting $i$ from the string if $a_i=0$, so for example $(1,0,0,3,0,0,0,1)$ would be $14^38$ (all the vectors in the actual problem had a large number of zeros, one of the reasons to change to this more concise notation). Most of the time all of the non-zero numbers were $1$s, so they all ended up looking like integers.

Naturally the first time I actually did a calculation in this notation, I wanted to remind anybody reading that the numbers had to be read back as these vectors, not as integers. Unfortunately, the first line was:

$$(0,0,0,1,1,1,0,0,0)+(1,0,0,0,1,0,0,0,1)-(1,0,0,0,1,1,0,0,0)=(0,0,0,1,1,0,0,0,1)$$

or in my notation:

$$456+159-156=459$$

• Maybe you accidentally wrote one of the sixes or nines upside-down? – Joe Z. Dec 17 '12 at 23:44

$\sin(x) = 0$

Thus we have either $x = 0$ or $\sin = 0$. A function cannot be equal to a number, therefore we must have x = 0.

I knew someone who once got as far as the first step, although in their defense I think it was just a temporary brain fart. The conclusion is correct if you're working with a restriction of the sine function to, say, $(-\pi, \pi)$.

Here is my example: $$\lim_{n\to\infty}\frac{1+2^2+3^3+\ldots+n^n}{n^n}=\lim_{n\to\infty}\left(\frac{1}{n^n}+\frac{2^2}{n^n}+\ldots+\frac{n^{n}}{n^n}\right)=0+0+\ldots+ 1=1.$$

• What's wrong with this one? – superAnnoyingUser Feb 16 '13 at 23:46
• @George Similar thing that is wrong with $\lim_{n\to\infty} \frac{n}{n} = \lim_{n\to\infty} \left( \frac{1}{n} + \frac{1}{n} + \cdots + \frac{1}{n} \right) = 0+0+ \cdots +0=0.$ – Ragib Zaman Feb 17 '13 at 14:13
• To spell out the problem, you can't interchange a limit with a sum when the number of terms in the sum involves the same variable that you're taking the limit with respect to. – Keshav Srinivasan Nov 2 '13 at 21:57
• @JonasMeyer No, the correct limit is 1. you can see it by squeezing the limit between 1 and $(n^1+n^2+\ldots n^n)/n^n$. – Artem Apr 25 '15 at 23:03
• Oh thanks @Artem, sorry for not checking better; I was misreading because of the other thread and taking all the exponents as $n$, so $1^n + 2^n +\cdots +n^n$ in the numerator instead of $1^1+2^2+\cdots+n^n$. Thanks for pointing out a good way to find this limit, too. I'll delete my wrong comments. – Jonas Meyer Apr 26 '15 at 1:43

Kepler's second law famously states that the radius vector from the sun to a planet will sweep out equal areas under equal times. His proof of this law included the following errors:

(1) He assumed that the velocity of the planet, as the planet traversed its orbit, was inversely proportional to the distance from the sun.

(2) Let $P_1P_2\dots P_{n+1}$ be points on an arc of the orbit of the planet, and such that the distances $|P_{i+1}-P_i|$ for $i=1,\dots,n$ are all equal to some small $\Delta s$. Let $S$ be the position of the sun, and let $r_i = |P_i -S|$ be the radial distance between the sun and the planet's position at $P_i$. Kepler then assumed that the area swept out by the radius vector from $S$, as the planet moved from $P_1$ to $P_n$, was proportional to the sum $(r_1+r_2\dots+r_n)\Delta s$.

Both these assumptions are wrong, but fortunately the effects of these errors cancel each other, and so Kepler was able to state his correct second law of planetary motion.

• Reference, please? – Willie Wong Feb 8 '13 at 12:51
• @WillieWong See C. H. Edwards, Jr: The Historical Development of the Calculus, p. 100. An entertaining version can also be found in Arthur Koestler: The Sleepwalkers, p. 331. – Per Manne Feb 8 '13 at 13:00
• My jaw dropped to the floor when I read this one. I think it's a bit outrageous that these historical facts are not as well known as the laws themselves. After all, to the layperson, these laws are important not for their (correct) content, but as icons of the scientific method. If their derivation was as flawed as this, then this iconic status is one big lie... – kjo Feb 8 '13 at 19:14
• It's possible, though, that Kepler had derived the result by some correct but circuitous method, then attempted to clean up and simplify the derivation for publication and failed. – Daniel McLaury Sep 18 '14 at 11:22
• @DanielMcLaury, I think it's more accurate to say that Kepler observed the result, rather than deriving it, as I commented to kjo a minute ago (math.stackexchange.com/questions/260656/…). – Vectornaut Oct 31 '15 at 17:16

Old John's example is gorgeous, but consider famous freshman's dream $$(a+b)^p = a^p + b^p \pmod p .$$

Various things which are true because of complex numbers, could be derived incorrect way in reals, e.g. using symbols like $\sqrt{-2}$, etc.

In probability theory there are lot of issues with dependent random variables, which can still yield correct results.

Also, check out this: \begin{align} S(a,b) &= \sum_{k=a}^{b} 2^k\\ T(a) &= \sum_{k=a}^{\infty} 2^k = 2^a + 2\sum_{k={a+1}}^{\infty} 2^{k-1} = 2^a + 2T(a)\\ T(a) &= \frac{2^a}{1-2} = -2^a \quad(\text{sum of positive elements is negative!})\\ S(a,b) &= T(a) - T(b+1) = -2^a - (-2^{b+1}) = 2^{b+1}-2^a \end{align} and this:

\begin{align} \sum_{k=0}^{n} 2^k &= \frac{2^{n+1}-1}{1-2} \\ \frac{d}{d2}\sum_{k=0}^{n} 2^k &= \frac{d}{d2}\frac{2^{n+1}-1}{1-2}\quad(\text{differentiate over two!})\\ \sum_{k=0}^{n} k2^{k-1} &= \frac{1-(n+1)2^n+n2^{n+1}}{(1-2)^2} \end{align}

Cheers!

• For the last, you could first replace $2$ by $x$, differentiate, and replace $x$ by $2$ again, so how is that "wrong"? And for the "sum of positive elements is negative", this also happens in e.g. the $2$-adic numbers, where $1 + 2 + 4 + \ldots = -1$. – TMM Dec 17 '12 at 13:42
• @TMM This is how those equations got created ;-) Still, for most people it is not only strange, but wrong - we work with "normal" numbers, not 2-adic, and then the presented series does not converge at all, why should it yield a correct result? – dtldarek Dec 17 '12 at 13:54
• @dtldarek, I think the first equation involving $T(a)$ should be $$T(a) = \sum_{k=a}^{\infty}2^k = 2^a + 2 \sum_{k=a+1}^{\infty}2^{k-1} = 2^a + 2T(a).$$ – kjo Dec 17 '12 at 15:47
• These are not very good examples, because they actually can be (and are being) used reliably. (As opposed to cancelling digits, say.) – Phira Dec 17 '12 at 22:22
• It should also be pointed out the Freshman's dream example could be false if $n$ is not prime. For example, $$(1 + 3)^4 = 256 \equiv 0 \pmod{4}$$ but $$1^4 + 3^4 = 82 \equiv 2 \pmod{4}.$$ The freshman's dream (including the url to which you linked) deals only with the case of prime characteristic. – JavaMan Feb 7 '13 at 6:07

If $G$ is a group and $K,N$ are normal in $G$ with $K \subseteq N$ then $$G/N \cong (G/K)\large/\normalsize(N/K)$$ which is obviously true by just cancelling the terms on the rhs.

• Can this be made rigorous somehow? – YoTengoUnLCD Oct 31 '15 at 17:44
• @YoTengoUnLCD It's the 3rd isomorphism theorem. There are lots of proofs around. – Jemmy Nov 2 '15 at 23:57

Earlier, I asked my friend to simplify $\dfrac{\cos^2 (73) + \cos^2(17)}{\cos^2(63) + \cos^2(27)}$. Here is his work:

$$\frac{\cos^2(73) + \cos^2(17)}{\cos^2(63) + \cos^2(27)} = \frac{\cos^2(73 + 17)}{\cos^2(63 + 27)} = \frac{\cos^2{(90)}}{\cos^2(90)} = \frac{\cos^2}{\cos^2} = 1$$

A classical example due to Euler, I believe:

Notice that the roots of $\sin(x)$ are precisely the numbers $k \pi$ where $k$ is any integer. But the same is true of the product

$$x \left(1 - \frac{x^2}{\pi^2 1^2}\right) \left(1 - \frac{x^2}{\pi^2 2^2}\right)\ldots$$

so the two must be equal. The coefficient of $x^3$ in the product is $-\frac{1}{\pi^2} \sum_{n=1}^\infty \frac{1}{n^2}$, and the coefficient of $x^3$ in the Taylor series of $\sin(x)$ is simply $-\frac{1}{6}$. Therefore,

$$\sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}$$

If part of your brain is tempting you to think that this argument might be right after all, note that if you apply exactly the same reasoning to the function $\sin(\pi x)$ then you get the value $\frac{\pi^3}{6}$. Nevertheless, this is so eerie that I can't help but wonder if there's something to it...

• This is a good one, although it is a case of lack of proper rigor and justification (which hardly existed at the time) rather than simply invalid nonsense as in many of the other answers. There is definitely something to it. I do not understand your point at the end about $\sin(\pi x)$. – Jonas Meyer Dec 28 '12 at 7:21
• @Jonas Meyer: The "product formula" at the beginning is complete baloney; I know of nothing even close to it which is correct. If you apply the same argument to $\sin(\pi x)$, then the product formula involves terms of the form $(1 - \frac{x^2}{n^2})$ and so the coefficient of $x^3$ is $-\sum \frac{1}{n^2}$. On the other hand the coefficient of $x^3$ in the Taylor series of $\sin(\pi x)$ is $-\pi^3/6$. Actually, it seems that if you apply the argument to $\sin(ax)$ for an appropriately chosen value of $a$, you get get any value for the sum that you want. – Paul Siegel Dec 28 '12 at 16:52
• That is not true. The product is valid on the entire complex plane, converging to $\sin$ uniformly on compact subsets. I now see your point about $\sin(\pi x)$; I misread your exponent, which is off because the correct product for $\sin(\pi x)$ has $\pi x$ as the first term rather than just $x$. You are correct that the method of argument for why the product is valid is incorrect (basically there isn't any here), and therefore easily leads to other incorrect products like your implied one for $\sin(\pi x)$. Alternatively, note that $e^x\sin(x)$ also has the same zeros. – Jonas Meyer Dec 28 '12 at 17:00
• Really? This is going to lead to an afternoon spent with a complex analysis book... – Paul Siegel Dec 28 '12 at 17:02
• I know I've seen this in Conway's Functions of one complex variable if you happen to have that handy. Here's something just found by Googling: ams.org/bookstore/pspdf/gsm-97-prev.pdf – Jonas Meyer Dec 28 '12 at 17:04

My "favorite" error with complex numbers is $$\frac{i}{i}=\frac{\sqrt[2\,\,]{-1}}{\sqrt[2]{-1}}=\sqrt[2\,\,]{\frac{-1}{-1}}=\sqrt[2\,\,]{1}=1.$$

• Whats wrong with that? The answer could have been achieved directly, apart from that, I don't actually see anything wrong? – ADP Dec 20 '12 at 1:11
• @ADP: $\dfrac{\sqrt{a}}{\sqrt{b}}=\sqrt{\dfrac{a}{b}}$ and $\sqrt{a}\sqrt{b}=\sqrt{ab}$ are identities that hold when $a$ and $b$ are positive and $\sqrt{x}$ is defined to be the positive square root of a positive number $x$. When square roots are extended to negative (or even complex) numbers, first one has to be careful about which square root, and secondly one has to give up hope of such identities always holding. E.g., consider the classic nonsense line $-1=\sqrt{-1}\sqrt{-1}=\sqrt{(-1)(-1)}=\sqrt{1}=1$. Related: math.stackexchange.com/questions/84436. – Jonas Meyer Dec 20 '12 at 3:53
• @Jonas Meyer, thanks. I didn't realize the power laws were constrained like that, to me they were just identities. Doesn't that then undermine the proof for Euler's Formula, where $e^{-ix}$ is divided by $e^{-ix}$ (once the derivative is proved to be constant), yielding the desired identity? – ADP Dec 20 '12 at 4:02

Slightly contrived:

Given $n = \frac{2}{15}$ and $x=\arccos(\frac{3}{5})$, find $\frac{\sin(x)}{n}$.

$$\frac{\sin(x)}{n} = \mathrm{si}(x) = \mathrm{si}x = \boxed{6}$$

One example from me:

$$\sqrt{5 \frac{5}{24}} = 5 \sqrt{\frac{5}{24}}$$ $$\sqrt{12 \frac{12}{143}} = 12 \sqrt{\frac{12}{143}}$$

• My first reaction was that this should have been generalized to, say, any positive $x \neq 1$, but then I realized that in the general form, the $+$ on the LHS is no longer implicit, $$\sqrt{x + \frac{x}{x^2 - 1}} = x\sqrt{\frac{x}{x^2 - 1}}\;,$$ which makes the maneuver less amusing somehow. – kjo Dec 17 '12 at 18:05
• There's no such thing as implicit +. That's multiplication, and because of that, wrong. – Karoly Horvath Dec 18 '12 at 1:28
• @yi_H I would argue that a mixed number has an implicit +. – Code-Guru Dec 18 '12 at 3:57
• an implicit +? maybe in elementary school...? – Jonathan Dec 18 '12 at 5:38
• probably... that would make it ambigous.. that's why you never use it to denote addition. No operator means multiplication. – Karoly Horvath Dec 19 '12 at 1:13

When I asked my student to get rid of irrationality in the denominator of fraction $$\frac{1}{\sqrt[3]{3}+\sqrt[3]{5}}$$ He gave an immediate solution $$\frac{1}{3^{1/3}+5^{1/3}}$$ What can I say, no roots no irrationalities :-)

I must confess, this example doesn't fit in the original citeria.

• The denominator is still irrational. – Brusko651 Nov 2 '13 at 22:06
• I'm not sure this really qualifies for this question. The question is about bad mathematical steps that lead to the correct answer. – Thomas Andrews May 10 '15 at 13:45

You all probably, no doubt, have seen the proof to the question: Is Hell Endo or Exothermic.

This one always makes me laugh...

Dr. Schambaugh, of the University of Oklahoma School of Chemical Engineering, Final Exam question for May of 1997. Dr. Schambaugh is known for asking questions such as, "why do airplanes fly?" on his final exams. His one and only final exam question in May 1997 for his Momentum, Heat and Mass Transfer II class was: "Is hell exothermic or endothermic? Support your answer with proof."

Most of the students wrote proofs of their beliefs using Boyle's Law or some variant. One student, however, wrote the following:

"First, We postulate that if souls exist, then they must have some mass. If they do, then a mole of souls can also have a mass. So, at what rate are souls moving into hell and at what rate are souls leaving? I think we can safely assume that once a soul gets to hell, it will not leave.

Therefore, no souls are leaving. As for souls entering hell, let's look at the different religions that exist in the world today. Some of these religions state that if you are not a member of their religion, then you will go to hell. Since there are more than one of these religions and people do not belong to more than one religion, we can project that all people and souls go to hell. With birth and death rates as they are, we can expect the number of souls in hell to increase exponentially.

Now, we look at the rate of change in volume in hell. Boyle's Law states that in order for the temperature and pressure in hell to stay the same, the ratio of the mass of souls and volume needs to stay constant. Two options exist:

If hell is expanding at a slower rate than the rate at which souls enter hell, then the temperature and pressure in hell will increase until all hell breaks loose. If hell is expanding at a rate faster than the increase of souls in hell, then the temperature and pressure will drop until hell freezes over. So which is it? If we accept the quote given to me by Theresa Manyan during Freshman year, "that it will be a cold night in hell before I sleep with you" and take into account the fact that I still have NOT succeeded in having sexual relations with her, then Option 2 cannot be true...Thus, hell is exothermic."

The student, Tim Graham, got the only A.

• Although this is a classic, I do not think this is a good answer for this question (wrong method, correct answer), or this site in general (focused on mathematics). – TMM Dec 18 '12 at 13:21
• I hate to be that guy (no pun intended) but that whole post is a work of fiction, see e.g. this. It's also, of course, off topic :) – guy Dec 18 '12 at 16:43
• And this whole thread is off topic from this entire site. A whole thread of incorrect proofs, please... – ADP Dec 19 '12 at 2:42

A classical example.

Cayley Hamilton Theorem states that for any matrix $A \in Mat(\mathbb R)_{n \times n}$, $A$ is a root of its characteristic polynomial $P_A(t)=det(A-tI)$.

Proof:

$P_A(A)=det(A-AI)=det(A-A)=det(0)=0$

A very common mistake in analysis.

Exercise: Let's $K\subset\mathbb{R}^{n}$compact and a function $f:K\to \mathbb{R}$ locally Lipschitz, i.e. for all $x$ in the compact $K$ there is an open set $V_x$ containing $x$ and a constant $L_x$ such that $$\left|\,f(u)-f(v)\,\right|<L_x \|u-v\|, \quad \forall u,v\in V_x$$ Proof that $f$ is too Lipschitz in all $K$.

"Proof:" Let $\{V_x\}_{x\in K}$ the open cover of $K$ where each $V_x$ is as in the hipotesis of exercise. As $K$ is compact there is a finite pen cover $\left\{V_{x_{_1}},\dots, V_{x_{_N}}\right\}$. Then for all $u,v\in K$ we have $$\left| f(u)-f(v) \right|<\max\left\{L_{x_{_1}},\dots,L_{x_{_N}}\right\}\cdot \|u-v\|, \quad \forall u,v\in K.$$

So just $L=\max\left\{L_{x_{_1}},\dots,L_{x_{_N}}\right\}$ to a constant that is valid for all $K$. Then $f$ is too Lipschitz in all $K$.

• @George At least two things wrong I can see are that this proof seems to assume that $K$ is connected, and also the $u,v$ went from being in each $V_x$ to magically being able to be picked from $K$. To fix the second issue, we need to connect up the $u$ and $v$ via a path through the $V_x$ balls. For the first one, prove the theorem assuming $K$ is connected, and then show being Lipschitz on all connected components of $K$ implies the result. – Ragib Zaman Feb 17 '13 at 14:11
• @RagibZaman "connect up the u and v via a path through the Vx balls" What if K is not convex? – Jisang Yoo Oct 18 '13 at 23:44

There is a lot of treatment with little rigor around the first infinitesimal calculations. For example consider a circle of radius $r$, we can approximate it's area by filling it with equal triangles.

The area of each triangle is given(approximately) by $lr/2$, where $l$ is the base of the triangle. If we have $n$ triangles, the sum of their areas is given by $nlr/2$. By increasing the number of triangles to infinity, the sum of the bases of the triangles approximates the length of the circumference, i.e, if $n\rightarrow\infty$ then $nl\rightarrow2\pi r$. Thus, the sum of the areas of the triangles tends to $2\pi r^2/2 = \pi r^2$, which is the area of the circle.

The result is correct but we calculates $\infty\cdot 0$ with almost no rigor at all.

• There is something about this kind of arguments that I always found awkward. I mean some of us have seen that picture that goes like "here's a right triangle with sides of length 1, 1, and square root of 2. we draw a staircase that approximates the hypotenuse. therefore square root of 2 is 2". – Jisang Yoo Oct 18 '13 at 22:57
• @JisangYoo There is something fundamentally different between lengths and areas. If shape A contains shape B, we know that area(A)>area(B), but we do not always have that perimeter(A)>perimeter(B). I think that's the basic idea behind why nonrigorous arguments about area, like the OP's, work, while the same sort of reasoning, like the one you mentioned, doesn't. – Akiva Weinberger Apr 19 '15 at 20:46

This happened to me last week with a quiz I gave to my Algebra 2 class doing radical equations.

Solve $\sqrt{-5x+35}+7=x$

WRONG $$\sqrt{-5x+35}=x-7$$ $$-5x+35=x^2-49$$ $$0=x^2+5x-84=0$$ $$0=(x+12)(x-7)$$ Thus $x=-12, 7$. Checking for extraneous solutions yields the only solution as $x=7$

RIGHT $$\sqrt{-5x+35}=x-7$$ $$-5x+35=x^2-14x+49$$ $$0=x^2-9x+14$$ $$0=(x-2)(x-7)$$ Thus $x=2,7$. Checking for extraneous solutions yields the only solution as $x=7$

I assumed most of them were cheating.... I was wrong!

• You assumed they were cheating because they all used the same wrong method, so you thought they copied? How do you know you were wrong? – Daniel Fischer Feb 19 '14 at 11:19
• A couple of early quizzes I graded had the first two lines, or variations of them, but didn't finish the step by step method and just circled $x=7$ as the answer. It is a basic Algebra 2 class, so I definitely have students who do this often. But after a while, I noticed that most students made that error above. The students I asked afterward all said the same thing; I thought when you squared (x-7) you got $x^2-49$. – Eleven-Eleven Feb 19 '14 at 12:01

Another one I came across was a function composition problem.

Let $g(x)=x^2.$ Find $(g\circ g)(x)$.

Well it should be $$(g\circ g)(x)=g(g(x))=g(x^2)=(x^2)^2=x^{2\cdot{2}}=x^4$$ But of course I should have caught that my students would do the "natural thing" and say $$(g\circ g)(x)=g(x)\cdot g(x)=x^2\cdot x^2=x^{2+2}=x^4$$

I blame myself for not catching this one, but.....

By linearity

$$\log(1+2+3) = \log(1)+\log(2)+\log(3).$$

(just don't try to generalize this)

• $\log\left(1+1+2+4\right)=\log\left(1\right)+\log\left(1\right)+\log\left(2\right)+\log\left(4\right)$ and $\log\left(1+1+1+2+5\right)=\log\left(1\right)+\log\left(1\right)+\log\left(1\right)+\log\left(2\right)+\log\left(5\right)$ – Joshua Tilley Apr 27 '18 at 11:29

Does this count? It can be shown that following the steps will give the correct answer, but the steps themselves are sometimes questionable. Let $y=(x-1)^3(x-2)^5(x-3)^7$. Find $\dfrac{dy}{dx}$.

Take the log of both sides. We get $$\log y=3\log(x-1)+5\log(x-2)+7\log(x-3).$$ Thus $$\frac{1}{y}\frac{dy}{dx}=\frac{3}{x-1}+\frac{5}{x-2}+\frac{7}{x-3},$$ and therefore $$\frac{dy}{dx}=3(x-1)^2(x-2)^5(x-3)^7 + 5(x-1)^3(x-2)^4(x-3)^7+7(x-1)^3(x-2)^5(x-3)^6.$$ Simple, generalizes, true for all $x$, including many $x$ at which log is not defined.

Remark: One can find many examples in Euler: formal manipulations that lead to the correct answer through in principle unjustified steps. About this, Euler wrote something like "Sometimes my pencil is more clever than I am."

• That's a standard method to prove polynomial identities by proving them for enough special values. – Phira Dec 17 '12 at 22:40
• What's wrong with that? They taught us this in secondary! – The Chaz 2.0 Dec 17 '12 at 22:40
• en.wikipedia.org/wiki/Logarithmic_differentiation – NeverBeenHere Dec 17 '12 at 22:57
• Certainly it is familiar. However, it is (for functions defined on the reals) formally incorrect, since for example at $x=0.5$ we are using the logarithm of three negative numbers. – André Nicolas Dec 17 '12 at 23:01
• @Nur For negatives you can multiply both sides by $-$ and do exactly the same computations, the minuses cancel. Why the result holds at $x=1,2,3$ is a little more subtle in general, in this case it is easy to argue because everything is polynomial...Formally, when we apply logarithmic differentiation to $y=f(x)$ we should actually apply it to $sy=s f(x)$ where $s(x)$ is the sign of $f(x)$... – N. S. Dec 20 '12 at 17:19

Recently seen:

Given $\gcd(a, b) = c$ we have $c\mid a$ and $c \mid b$, so $$(c\mid a) \cdot (c \mid b) = (c \cdot c) \mid (a \cdot b) = c^2 \mid ab,$$ hence $c^2 \mid ab$.

• If you think about the meaning, $\cdot$ does really "distribute over" |. – Utku Alhan Mar 18 '14 at 18:19
• @UtkuAlhan This is not distribution, the left side contains $c$ while the right has $c^2$. I'm not saying you cannot make it formal, after all, the result is true. I'm just saying that this particular derivation (without any additional comment) is wrong. – dtldarek Mar 18 '14 at 18:24
• Yes, distribution was the wrong word to use. You're right. Thanks for the correction. This particular derivation is wrong of course: for starters, what does (statement 1) = (statement 2) mean? – Utku Alhan Mar 18 '14 at 18:32

I'm learning right now why you don't ask first-year calculus students to determine

$$\lim_{x \to -\infty} \frac{x}{\sqrt{x^2+1}}:$$

because you'll get back a bunch of

$$\frac{x}{\sqrt{x^2+1}} \to \frac{-\infty}{\infty} = \frac{-\not\infty^1}{\not \infty^1} = -1.$$

## protected by Eric NaslundDec 18 '12 at 17:55

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).


text:
# Rigorous proof of limits of sequences (3)

1. Jan 8, 2010

### kingwinner

1. The problem statement, all variables and given/known data

But I think the definition is as follows:
Let an be a sequence of real numbers. Then an->a iff
for ALL ε>0, there exists an integer N such that n≥N => |an - a|< ε.

The definition says that it has to be true for ALL ε>0, but in the example above, they just let ε to be a rational number with a very specific form. To me, the proof looks incomplete. They only proved the statement for the case of ε being rational number with that very specific form, but how about the case when we're given an irrational ε, or other rational ε that cannot be expressed in that specific form?
Is the proof correct or not?

2. Relevant equations
N/A

3. The attempt at a solution
Shown above.

Can someone explain this? Thanks for any help! :)

Last edited: Jan 8, 2010
2. Jan 8, 2010

### snipez90

Well I'm assuming k is a real number, in which case there is nothing wrong with the proof (verify this on your own). However, there is a much simpler estimate that could have been made, namely

$$\frac{1}{n+1} \leq \frac{1}{N+1} < \varepsilon$$

provided that $N > \frac{1}{\varepsilon}-1.$

Out of curiosity, which text are you learning from?

3. Jan 8, 2010

### kingwinner

I looked at my book again and the context before the example highly suggests that k is a natural number (or 0). It says "it suffices to consider only values for ε of the form (1/2)10-k...agree with L to at least k decimals of accuracy."

If this is the case, is the proof still correct? If so, why?

(I understand your much simpler proof, but I just want to know whether "the proof provided above" is complete or not.)

The book from which this example is taken is Real Analysis by Donsig.

4. Jan 8, 2010

### snipez90

Ah OK, well the author is choosing not to consider all real epsilon, which is weird. I would say it doesn't matter much since if we let epsilon -> 0 we can still make our sequence arbitrarily close to 1. Anyways it seems simpler to consider all real values of epsilon (> 0) and replace $\frac{1}{2}10^{-k} = \varepsilon$ with $\frac{1}{2}10^{-k} < \varepsilon.$

5. Jan 9, 2010

### HallsofIvy

Staff Emeritus
Given any $\epsilon> 0$, there exist k such that $(1/2)10^{-k}< \epsilon$. Then if $|a_n- L|< (1/2)10^{-k}$, it is less than $\epsilon$ so this is sufficient.